Problema Anno luce: execution timed out

Aiuto
1

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 :sob:
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;

    if(dprec < query)
        it=upper_bound(it,distanze.end(),query*query);
    else
        it=upper_bound(distanze.begin(),it,query*query);

    dprec=query;

    out<<it-distanze.begin()<<endl;
}
2

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.

3

Grazie mille, risolto.
La distinzione in realtà l’avevo introdotta proprio per risparmiare tempo restringendo l’intervallo di ricerca ahahah.

4

Il problema era dovuto all ’ upperbound () ?

5

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 :slight_smile:

6

Ho fatto un’unica ricerca come hai detto te. E al posto di fare it=… e poi stamparlo ho scritto direttmente l’upper_bound - distanze.begin() nel cout

7

Capito, ti ringrazio :slight_smile:

8

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 :smile:) ad un 0.192. Grazie mille hahahah