# Aiutino per Vasi **URL:** \ **Category:** Aiuto\ **Created:** [29 Aprile 2014, 10:04am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800 "2014-04-29T10:04:58Z")\ **Posts on this page:** 20\ **Page:** 3
**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\ **Post date:** [16 Agosto 2014, 8:44am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/41 "2014-08-16T08:44:53Z")
La struttura da usare non è; deque \ V[N]; Ma vector\< deque \ \> V; decks.resize(sqrtN); for(int i = 0; i \< sqrtN; i++) decks[i].reserve(sqrtN); o al limite deque \ 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. Se no passa il sorgente su fb che lo guardo :3 ---
**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\ **Post date:** [16 Agosto 2014, 9:06am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/42 "2014-08-16T09:06:13Z")
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 ---
**Author:** ![E.rocchi1955](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/e/e19b73/32.png) [@E.rocchi1955](https://forum.olinfo.it/u/E.rocchi1955)\ **Post date:** [16 Agosto 2014, 9:38am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/43 "2014-08-16T09:38:10Z")
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. ---
**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\ **Post date:** [16 Agosto 2014, 9:51am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/44 "2014-08-16T09:51:03Z")
>     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. ---
**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\ **Post date:** [16 Agosto 2014, 12:21pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/45 "2014-08-16T12:21:12Z")
> 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... ---
**Author:** ![E.rocchi1955](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/e/e19b73/32.png) [@E.rocchi1955](https://forum.olinfo.it/u/E.rocchi1955)\ **Post date:** [16 Agosto 2014, 12:56pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/46 "2014-08-16T12:56:26Z")
Niente da fare, la situazione é peggiorata.Qualcuno lo ha risolto senza usare i fast  I/O? ---
**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\ **Post date:** [16 Agosto 2014, 1:04pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/47 "2014-08-16T13:04:46Z")
> Niente da fare, la situazione é peggiorata.Qualcuno lo ha risolto senza usare i fast >  I/O? > > E.rocchi1955 Io ahahaha ---
**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\ **Post date:** [16 Agosto 2014, 1:27pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/48 "2014-08-16T13:27:01Z")
> > 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\ 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 ---
**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\ **Post date:** [16 Agosto 2014, 2:25pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/49 "2014-08-16T14:25:06Z")
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). ---
**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\ **Post date:** [16 Agosto 2014, 3:32pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/50 "2014-08-16T15:32:11Z")
> 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/ ---
**Author:** ![EmanueleRossi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/emanuelerossi/32/42_2.png) [@EmanueleRossi](https://forum.olinfo.it/u/EmanueleRossi)\ **Post date:** [16 Agosto 2014, 8:16pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/51 "2014-08-16T20:16:04Z")
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… ---
**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\ **Post date:** [16 Agosto 2014, 9:13pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/52 "2014-08-16T21:13:19Z")
Probabilmente l’algoritmo corretto è quello per vasi2 (che ha 2 secondo di tempo limite), però non ho idea di come si possa risolvere ---
**Author:** ![Degiac](https://forum.olinfo.it/user_avatar/forum.olinfo.it/degiac/32/9_2.png) [@Degiac](https://forum.olinfo.it/u/Degiac)\ **Post date:** [17 Agosto 2014, 10:20am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/53 "2014-08-17T10:20:58Z")
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? ``` #include #include #include #include using namespace std; int main() { ifstream in(“input.txt”); ofstream out(“output.txt”); int N, M; in >> N >> M; int radN = sqrt(N); vector > 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]; vasi[arr1].erase(vasi[arr1].begin() + pos1); while(arr1 < arr2) { vasi[arr1].push_back(vasi[arr1+1].front()); vasi[++arr1].pop_front(); } while(arr1 > arr2) { vasi[arr1].push_front(vasi[arr1-1].back()); vasi[–arr1].pop_back(); } vasi[arr1].insert(vasi[arr1].begin() + pos2, value); } } out << “\n”; return 0; } ``` ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [16 Giugno 2017, 10:28am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/54 "2017-06-16T10:28:03Z")
Riapro la discussione dopo quasi 3 anni 😅 Questo è il mio codice [https://pastebin.com/KTRjPcDF](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 😄 ) ---
**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\ **Post date:** [16 Giugno 2017, 10:42am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/55 "2017-06-16T10:42:54Z")
Accedi male al primo elemento della prima deque 😛 Dovrebbe essere `[primadeq][primo%rad]` non `[primadeq][primo/rad]` ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [16 Giugno 2017, 10:49am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/56 "2017-06-16T10:49:12Z")
Quello è vero, ma anche se le correggo, e aggiungo un return 0 subito dopo l’inserimento dei valori nella deque mi da lo stesso errore ---
**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\ **Post date:** [16 Giugno 2017, 11:06am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/57 "2017-06-16T11:06:12Z")
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 😛 PS: buon appetito 🍫 ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [16 Giugno 2017, 11:26am UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/58 "2017-06-16T11:26:28Z")
> [@frakkiobello](#): > > 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 😄 ) A questo mi riferivo, quale sarebbe l’istruzione da fare : A.resize(rad)?[quote=“VashTheStampede, post:57, topic:3800”] PS: buon appetito 🍫 [/quote] Avevo fame prima di leggere la tua risposta… 😡 😉 ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [16 Giugno 2017, 12:29pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/59 "2017-06-16T12:29:08Z")
> [@frakkiobello](#): > > A.resize(rad) 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? ---
**Author:** ![VashTheStampede](https://forum.olinfo.it/user_avatar/forum.olinfo.it/vashthestampede/32/10_2.png) [@VashTheStampede](https://forum.olinfo.it/u/VashTheStampede)\ **Post date:** [16 Giugno 2017, 12:43pm UTC](https://forum.olinfo.it/t/aiutino-per-vasi/3800/60 "2017-06-16T12:43:30Z")
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 🙂 [Pagina precedente](https://forum.olinfo.it/t/aiutino-per-vasi/3800.md?page=2) [Pagina seguente](https://forum.olinfo.it/t/aiutino-per-vasi/3800.md?page=4)