Ciao a tutti, ho provato a risolvere il problema Anno Luce ma ho avuto dei problemi nel tempo di esecuzione. Tutti i risultati che non vanno in timed-out dannno risultato corretto tranne 4 test.
Il mio codice e’ qui : https://pastebin.com/NmU4tHCX
Comunque il problema è la ricerca del numero di stelle che puoi raggiungere, perché tu stai utilizzando una ricerca di tipo lineare quindi O(n) e dovresti invece cercare di portarla ad un O(logN). Un piccolo suggerimento: quando svolgi degli esercizi qui sul forum controlla sempre i suoi tag, anche se effettivamente in gara non vengono mostrati quindi sarebbe come ottenere un indizio “illegalmente”.
Ho visto dall’inizio il tag della binary_search ma non ho capito a che serve la ricerca binaria in questo esercizio…
Potresti tenere le distanze delle stelle ordinate che inizialmente ti porta uno rallentamento in quanto devi appunto ordinarle O (nlogn) ma successivamente per ogni q tramite le ricerca binaria potrai trovare la risposta il O (logn) e non O(n) , cambiano la complessità attuale da O (q*n) ad O (NlogN + q*logn) , che nel caso in cui q abbia un valore molto maggiore a n diventa molto conveniente
Grazie @frakkiobello.
Ho implementato l’ordinamento e la ricerca binaria.
Ho risolto tutti i problemi di timed out ma restano “rossi” per l’output non corretto…
Qui c’è il mio nuovo codice : https://pastebin.com/3WtR6yGV
Temo sia overflow: ogni coordinata può arrivare fino a 2^{30}, quindi quando fai X[i]*X[i] arrivi a 2^{60} che esce dagli int 