Ciao a tutti,
io ho risolto il problema anno luce utilizzando la ricerca binaria in modo da ottimizzare i tempi. Il problema è che nonostante questo continuo ad avere “Execution Timed Out” in alcuni task
Ho anche introdotto un piccolo accorgimento per velocizzare ulteriormente il processo ma senza successo.
Il codice è questo:
for(int i=0;i<n;i++){
in >> x >> y >> z;
distanze.push_back(xx + yy + z*z);
}
sort(distanze.begin(),distanze.end());
in >> q;
dprec=0;
it=distanze.begin();
it++;
for(int i=0;i<q;i++){
in >> query;
Riusciresti a postare tutto il codice, possibilmente con il link a pastebin, mi sembra molto strano che con la ricerca dicotomica l’algoritmo vada fuori tempo, dovresti cavartela con 0,2 sec . Per la distanza dovrebbe bastare fare così;
return upper_bound(distanza.begin(), distanza.end(), D) - distanza.begin();
Evitando la distinzione dei 2 casi.
Quando devi eseguire output “multipli”, cerca di evitare endl e utilizza piuttosto '\n', questo perché std::endl non solo fa andare a capo il testo ma si preoccupa anche di fare un “flush” del buffer dell’output, operazione “costosa” se eseguita come in questo problema fino a 100 000 volte
Onestamente non ero a conoscenza di questo particolare che effettivamente è molto rilevante, per esempio in suffissi ( https://cms.di.unipi.it/#/task/suffissi/statement ) usando lo stesso algoritmo si passa da uno 0.996 (con limite di tempo a 1 sec ) ad un 0.192. Grazie mille hahahah