Buongiorno. Ho giusto oggi tentato di risolvere il problema “L33t H4xX0R (password)”. Le assunzioni prevedono fino ad un massimo di 10 milioni di numeri presi da input, e fin qui, nulla di problematico. Il problema sorge quando questi numeri che devono essere letti sono di tipo Long Long. Nonostante io abbia risolto il problema totalizzando 100/100 punti, il tempo impiegato è troppo alto e non mi soddisfa, così tramite varie prove, ho scoperto che ben 3.2 di quei secondi utilizzati vengono impiegati dalla lettura da file. Ho provato infatti a sottomettere solamente questo codice, che legge da file e niente di più:
#include <fstream>
int N;
long long K;
long long x;
int main()
{
std::ifstream in("input.txt");
std::ofstream out("output.txt");
in >> N >> K;
for(int i=0; i<N; i++)
in >> x;
return 0;
}
Cosa sbaglio? Ho anche provato la corrispettiva lettura da file tramite fscanf, ma i risultati non cambiano. Invece, sostituendo i tipi di K e X da long long ad int, tutto avviene molto velocemente (anche se ovviamente leggerà numeri errati).
Non sbagli nulla, è normale. Esistono alcuni metodi come getchar_unlocked() e putchar_unlocked() che restituiscono un char preso da file in modo molto veloce, sta a te poi convertirlo.
Sottolineo che il time limit è pensato per i metodi che hai utilizzato precedentemente.
Senza dover utilizzare i più scomodi get/putchar_unlocked(), è una buona pratica aggiungere nel tuo codice le righe in.tie(0); in.sync_with_stdio(0); per velocizzare l’input (a patto che tu non stia cercando di risolvere un problema interattivo in console, categoria che non penso sia presente qui sul cms).
Conoscevo il metodo “sync_with_stdio”, ma anche mettendolo non cambiava quasi nulla; buon a sapersi invece che esista anche il “tie”.
Proverò anche con getchar e putchar per vederne le differenze.
Se è davvero normale, allora mi rimane il dubbio: come hanno fatto le persone in classifica a metterci così pochi secondi? Ci sono due persone che in 0.7 secondi riescono a leggere da file ed eseguire l’algoritmo di risoluzione. Proverò a svolgere qualche test.
Beh. Se la lettura da file ci mette 4 volte tanto il tempo di qualcuno in classifica, allora qualche trucco particolare esiste. E comunque sono appena entrato in classifica
