for(int i = 0; i < sqrtN; i++) decks[i].reserve(sqrtN);
o al limite deque <int> V[sqrtN];
Usare un vettore di N di sqrtN elementi non ha senso se usi la sqrt-decomposition
Per il fatto del timeout, ad occhio non vedo errori, magari mettilo su pastebin o indentalo meglio, non mi va di diventare cieco per leggere il codice ahah, e magari fai due funzioni, una per l'update e una per la query, così diventa ancora più leggibile.
grazie I vector non li sò usare,sono più veloci? Se dimensiono a sqrtN+1 mi dice che violo i limiti di memoria con rad++ invece va…alcuni casi ora sono più veloci ed altri più lenti ma va comunque in timeout.
Ti conviene fare il resize a sqrtN+1. Comunque a occhio neanch'io vedo errori. Prova a rimandarlo più volte e vedi se lo prende
Lawliet
Si io davo per scontato il +1 anche perchè è ovvio che non puoi creare ad esempio 2 vettori di 1,4142135623...
I vector non li sò usare,sono più veloci?
E.rocchi1955
Comunque no non cambia niente se usi i vector, anzi in realtà sono più rapidi i vettori classici in certi casi, ma con i vector hai la comodità che puoi ridimensionare il vettore quando ti pare.
grazie :-) I vector non li sò usare,sono più veloci? Se dimensiono a sqrtN+1 mi dice che violo i limiti di memoria con rad++ invece va...alcuni casi ora sono più veloci ed altri più lenti ma va comunque in timeout.
E.rocchi1955
Prova a dichiararli come variabili globali e non dentro il main...
Niente da fare, la situazione é peggiorata.Qualcuno lo ha risolto senza usare i fast
I/O?
E.rocchi1955
Io ahahaha
mark03
Io anche, comunque ora che ho visto il codice: prova a cambiare:
for(a=0;a<N;a++)V[a/rad].push_back(a);
con:
for(int i = 0; i < rad; i++) { V[i].resize(rad); int k = i * rad; for(int j = 0; j < rad; j++) { V[i][j] = k+j; } }
per il resto mi sembra corretto nel container vector, l'uso del push_back influisce molto nelle prestazioni, non so se vale la stessa cosa per il container deque, ma tu prova con il codice che ti ho dato e vedi se cambia
Invece di fare resize(dim) e poi inserire elementi “a mano” accedendo all’indice desiderato, un modo più carino è usare comunque push_back però facendo una chiamata iniziale a reserve(dim). In questo modo si ha comunque il beneficio introdotto da resize() ovvero di non dover “saltuariamente” riallocare l’array se un push_back va a finire lo spazio a disposizione, però il codice è più pulito in molti casi (come questo).
Invece di fare resize(dim) e poi inserire elementi "a mano" accedendo all'indice desiderato, un modo più carino è usare comunque push_back però facendo una chiamata iniziale a reserve(dim). In questo modo si ha comunque il beneficio introdotto da resize() ovvero di non dover "saltuariamente" riallocare l'array se un push_back va a finire lo spazio a disposizione, però il codice è più pulito in molti casi (come questo).
wil93
da quel che so io non cè il reserve per le deque per i vector si, si puo fare ma resta comunque più veloce il metodo con il resize con i vector: http://lemire.me/blog/archives/2012/06/20/do-not-waste-time-with-stl-vectors/
Comunque è normale che vada in Time-out, 1,5 secondi è un tempo un po limite con questo algoritmo, io l’ho dovuto inviare 4/5 volte perche prima alcuni casi mi andavano in timeout di 0,2 0,3 secondi. Dipende anche dal momente del server…a volte la stessa soluzione sarà piu velcoe altre piu lenta…
EDIT: Credo di aver capito il problema, vi dico subito EDIT2: Risolto
Ragazzi non riesco a capire perché mi dia signal 11 per qualche test case (5 per l’esattezza), non mi sembra di accedere ad aree di memoria inesistenti… Qualcuno può dare un’occhio al mio codice?
int main() { ifstream in(“input.txt”); ofstream out(“output.txt”);
int N, M; in >> N >> M; int radN = sqrt(N);
vector<deque<int> > vasi(radN+1);
for(int i = 0; i < N; i++) vasi[i/radN].push_back(i);
for(int i = 0; i < M; i++) { char com; int a, b; in >> com; if(com == ‘c’) { in >> a; int arr = a/radN; int pos = a%radN; out << vasi[arr][pos] << " "; } else { in >> a >> b; if(a == b) continue; int arr1 = a/radN; int pos1 = a%radN; int arr2 = b/radN; int pos2 = b%radN; int value = vasi[arr1][pos1];
Questo è il mio codice https://pastebin.com/KTRjPcDF , in tutti i testcase il risultato è “Execution killed with signal 11 (could be triggered by violating memory limits)”, anche se onestamente non capisco il perché, mi sono accorto che l’errore viene creato subito nel ciclo di input ma non riesco a capire il perché, alla fine eseguo solo push_back() su delle deque.
Un’altro fattore che non mi è chiaro al 100% è il perché fare il resize(), potrei gestirlo anche senza no?(o almeno io ci ho provato ma vedendo il risultato non sono così sicuro che si possa omettere )
Ah lol avevo letto male
Comunque hai dichiarato una deque< deque >, prima di inserire elementi dovresti fare un resize per dire “ehi guarda che ho rad deques”.
Per farti un esempio più stupido: è come aver ordinato uno scatolone di scatole di cioccolatini; lo scatolone è predisposto per tenere solo scatole di cioccolatini, non cioccolatini. Tu in questo momento stai inserendo cioccolatini nello scatolone facendo riferimento a delle scatole che ancora non ci sono
Ok così non mi da nessun errore di compilazione, ma tutti gli output sbagliati. Se provo a portarlo in locale (uso dev) mi crasha durante l’esecuzione, quello che mi lascia più perplesso sono però i tempi di esecuzioni, in quanto nel caso peggiore ho 0.130 sec che è sicuramente troppo poco, sto trascurando qualcos’altro?
In questo momento non sono a casa quindi non riesco ad aiutarti molto, però forse ci sono problemi quando lavori sulla stessa deque, nel senso che con i vari insert vai a sfasare le posizioni degli elementi e in quel modo con gli erase elimini qualcosa che non dovresti eliminare.
Prova a fare qualche test su elementi che occupano la stessa deque
I vector non li sò usare,sono più veloci? Se dimensiono a sqrtN+1 mi dice che violo i limiti di memoria con rad++ invece va…alcuni casi ora sono più veloci ed altri più lenti ma va comunque in timeout.
)
