c è anche un post in top , ma è presente una confusione tra le varie risposte
top https://codeforces.com/blog/entry/81467
La complessità temporale non è sempre affidabile come sembra, tutti i fattori costanti vengono ignorati e, come in questo caso, possono fare la differenza.
In particolare in questo problema il numero di iterazioni eseguite è \frac{n\cdot(n-1)}{2}\approx\frac{10^{10}}{2}=5\cdot10^9 che è un numero relativamente piccolo. Il motivo però per cui il programma è così veloce, è che queste istruzioni sono molto semplici per cui il processore può ottimizzare alcune parti:
- gli accessi all’array vengono tutti eseguiti sequenzialmente per cui il processore può facilmente salvare in cache gli elementi successivi,
- l’assenza di
ifpermette al processore di prevedere facilmente le istruzioni successive, - vengono utilizzate le istruzioni vettoriali AVX che combinate con
-funroll-loopspermettono di eseguire in parallelo 8 iterazioni alla volta.
Infine per consentire ai partecipanti di utilizzare python e java, il time limit è stato impostato abbastanza alto permettendo a questa soluzione di risolvere tutti i testcase.