Aiutino per Vasi


#41

La struttura da usare non è;
deque <int> V[N];
Ma

vector< deque <int> > V;

decks.resize(sqrtN);

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.

Se no passa il sorgente su fb che lo guardo :3

#42

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

#43

grazie :slight_smile: 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.


#44
    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.

#45
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...

#46

Niente da fare, la situazione é peggiorata.Qualcuno lo ha risolto senza usare i fast

 I/O?

#47
Niente da fare, la situazione é peggiorata.Qualcuno lo ha risolto senza usare i fast
 I/O?

E.rocchi1955

Io ahahaha

#48
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

#49

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).


#50
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/

#51

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…


#52

Probabilmente l’algoritmo corretto è quello per vasi2 (che ha 2 secondo di tempo limite), però non ho idea di come si possa risolvere


#53

EDIT: Credo di aver capito il problema, vi dico subito :slight_smile:
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 <fstream>
#include <deque>
#include <vector>
#include <cmath>

using namespace std;

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];

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;
}




#54

Riapro la discussione dopo quasi 3 anni :sweat_smile:

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 :smile: )


#55

Accedi male al primo elemento della prima deque :stuck_out_tongue:
Dovrebbe essere [primadeq][primo%rad] non [primadeq][primo/rad]


#56

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


#57

Ah lol avevo letto male :joy:
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 :stuck_out_tongue:

PS: buon appetito :chocolate_bar:


#58

A questo mi riferivo, quale sarebbe l’istruzione da fare : A.resize(rad)?[quote=“VashTheStampede, post:57, topic:3800”]
PS: buon appetito :chocolate_bar:
[/quote]

Avevo fame prima di leggere la tua risposta… :rage: :wink:


#59

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?


#60

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 :slight_smile: