Este tipo de programas tienen trampa y es que se ciñen a unos requisitos en cuanto a tiempo de ejecución muy ajustados. Las soluciones generales no suelen dar buenos resultados.
Sincronización I/O
Lo primero que debes hacer es optimizar la entrada/salida. Por defecto, en C++ la I/O propia de C++ está sincronizada con la heredada de C. Esto impone una latencia que penaliza en exceso los tiempos de ejecución del programa.
Para desincronizar la entrada/salida basta con ejecutar:
std::ios_base::sync_with_stdio(false);
Puedes encontrar un ejemplo aquí
Como puedes ver, desactivar el sincronismo mejora los tiempos de lectura (en el caso del ejemplo la lectura es unas 4 veces más rápida)
Eso sí, al desactivar la sincronziación deja de ser seguro mezclar lecturas de stdio
y de cin
, así como las escrituras de stdout
y cout
.
Memoria dinámica
Por otro lado, debes intentar es reducir las reservas de memoria dinámica al máximo. Hacer una reserva de memoria dinámica es un proceso lento y laborioso que se come unos preciados ciclos de reloj... si se acaban haciendo reservas innecesarias, el tiempo se escapará entre tus dedos.
En tu caso es probable que el vector arr
se esté redimensionando innecesariamente varias veces. Piensa que el árbitro puede llegar a meter 10k elementos o más en el array (el número máximo suele venir indicado).
Eliminar las reservas innecesarias de memoria es tán sencillo como llamar a reserve
:
vector<long long int> arr;
arr.reserve(10000); // Maximo de elementos
Claro que, si te fijas, en tu caso estás creando un array para cada test. Eso implica que, para cada test, hay que crear un array (con la correspondiente reserva de memoria inicial) y destruir dicho array. Nuevamente es un trabajo totalmente innecesario.
Es preferible crear el array una sola vez y reutilizarlo en cada caso de prueba
vector<long long int> arr;
arr.reserve(10000); // Maximo de elementos
for (int o = 1; o<=t; o++){
// ...
arr.clear();
}
Vale, nuevo problema, hay que llamar a clear
al final de cada caso para vaciar el array ... nuevamente es un trabajo que podemos eliminar con algunos cambios:
vector<long long int> arr;
arr.resize(10000);
for (int o = 1; o<=t; o++){
int n;
cin>>n;
int cont = 0;
bool esDivisible = false;
for (int i = 0; i<n; i++){
cin>>arr[i];
}
for(int i=0;i<n;i++){
cont = 0;
for(int j=0;j<n;j++){
if(arr[j]%arr[i]==0){
cont++;
}
if(cont == n){
esDivisible = true;
break;
}
}
if(esDivisible){
break;
}
}
Ahora no llamamos a reserve
sino a resize
. Esto hace que el vector automáticamente se llene de 10000 elementos con valor inicial 0. En cada caso de prueba utilizaremos únicamente n
elementos, el resto nos da igual que existan o no ya que no vamos a acceder a ellos.
Vaya, resulta que ahora estamos inicializando todos los elementos del array a 0 para, posteriormente, dar a algunos de esos elementos un valor válido. Quizás debiéramos evitar esa inicialización a 0 para arañar algo al reloj. Lamentablemente std::vector
no te permite crear los elementos sin inicializarlos. Tenemos que pasar a usar punteros y arrays:
long long int * arr = new long long int[10000];
// ...
delete[] arr;
¿Y ahora?
Llegados a este punto hemos eliminado los cuellos de botella más evidentes, no obstante el programa podría ser todavía más óptimo aplicando algunos cambios.
Así, por ejemplo, se podrían evitar las iteraciones innecesarias.
Sabemos que un número x
no va a ser un divisor del conjunto arr
si el resto de alguna división es distinto de 0. Si se da esa circunstancia no tiene sentido seguir comprobando el resto de números ya que tenemos la certeza que x
no es solución:
int j;
for(j=0;j<n;j++){
if(arr[j]%arr[i]!=0) break;
}
if( j == n )
{
esDivisible = true;
break;
}
El programa podría seguir mejorándose, eliminando acciones innecesarias, cacheando resultados intermedios para evitar repetir cálculos, ... corre de tu cuenta el seguir investigando otras optimizaciones.
t
? Porque no se llamanumero_casos
? Hay que darle buenos nombres a las cosas para que los demas te entiendan facil.