Salve a tutti, ho provato a risolvere il problema Anno Luce (ois_annoluce), ma ho un problema riguardo al tempo di esecuzione. Tutti i task che non vanno in timeout, mi danno risultato corretto ma non capisco in che modo posso riuscire a velocizzare l’esecuzione del codice.
Il codice è il seguente: http://pastebin.com/aeSkkXeh
L’algoritmo in se è corretto, solo che non capisco come posso fare per ottimizzarlo e risucire a superare l’errore del timeout.
Quale è l’altro tipo di ricerca che conosci??
Dato lo scopo del problema (come anche evidenziato dal tag) la soluzione che ti permette di non incorrere in TLE è la ricerca binaria.
Sai di cosa si tratta o come funziona?
Se si, vorresti avere ulteriori suggerimenti?
La tua soluzione è di complessità attuale O(NQ) ossia per ogni query, devi scorrere l’Intero vettore di distanze.
Con l’approcio in ricerca binaria, la complessità diventa O(QlogN), in quanto usando un vettore di distanze sortato (tralascio il conteggio del sorting O(NlogN) ) è possibile adottare questo tipo di ricerca.
Fammi sapere se ti serve qualche indizio su come implementarla.
GiackAloZ
Ps: personalmente preferisco non calcolare le distanze usando la radice quadrata, ma elevare al quadrato gli anni richiesti dalle query, perché è leggermente più ottimizzato 
(ovviamente non dimenticare di usare dei long long int per memorizzare gli interi)
Ti ringazio per il consiglio, avevo già iniziato a sviluppare una variante tramite il Binary search ma non ho avuto molto tempo per completarlo, ma mi fa piacere che avevo puntato nella strada giusta. Comunque avevo già provato ad elevare al quadrato le distanze delle query senza calcolare la radice quadrata, ma in 3 dei casi del Sub Task 7 dava output non corretto, quindi ho preferito perdere qualche millesimo in calcoli e guadagnare in precisione, spero che la variante con il binary search funzioni
Certamente
Per qualsiasi cosa sono qui.
GiackAloZ