Fișierul intrare/ieșire interviu.in, interviu.out Sursă ad-hoc
Autor David Demetriad Adăugată de avatar demetriad-dagpag David Demetriad demetriad-dagpag
Timp de execuție pe test 0.15 sec Limită de memorie 5120 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Interviu

Mihnea tocmai a primit interviu o companie, numită Grebmoolb, pentru un post de inginer de software. Știind că examinatorii sunt oameni cu realizări impresionante în domeniul informaticii, dar și foarte exigenți, el s-a pregătit o lună întreagă pentru acest interviu. Lucrând probleme peste probleme, într-un mod haotic, el și-a dat seama în timpul interviului că a uitat tot ce învățase. “Jale mare! Să vezi că și ăștia mă pică! Mă las de facultate!” , așa și-a spus el. După ce s-a dezmeticit un pic, el a primit următoarea problemă:

Se dă o mulțime care inițial este vidă. În plus, se dau Q query-uri de tipul:

  • “1 x” – se inserează elementul x în mulțime dacă acesta nu există deja;
  • “2 x” – se șterge elementul x din mulțime dacă acesta există;
  • “3 x” – să se afișeze elementul care a fost inserat în mulțime imediat înaintea lui x, în ordine cronologică, dintre cele existente la
    momentul curent (dacă nu există un astfel de element, se va afișa -1);
  • “4 x” – să se afișeze elementul care a fost inserat în mulțime imediat după x, în ordine cronologică, dintre cele existente la momentul
    curent (dacă nu există un astfel de element, se va afișa -1);

În plus, la final se cere să se afișeze toate elementele mulțimii ( care au rămas după executarea tuturor operațiilor ) în ordinea în care au fost inserate.

Stă Mihnea și se gândește un pic și zice : “Gata, știu, se face cu vectori!”. Se apucă să codeze și după multă muncă și dedicare reușește în cele din urmă să rezolve problema și să obțină slujba! Toată lumea fericită! Încercați și voi… Până la urmă nu pare așa dificil să obții un post la Grebmoolb.

Date de intrare

Fișierul de intrare interviu.in conține pe prima linie se va regăsi numărul Q de întrebări. Pe următoarele Q linii se vor găsi cele Q întrebări sub forma descrisă în enunț.

Date de ieșire

În fișierul de ieșire interviu.out, pentru fiecare întrebare de tipul 3 sau 4, se va afișa pe câte o linie răspunsurile la acestea, în ordinea în care sunt primite întrebările. Pe ultima linie a fișierului se vor regăsi elementele rămase din mulțime în urma executării operațiilor, afișate în ordinea în care acestea au fost inserate, separate prin cate un spațiu.

Restricții și precizări

  • 1 ≤ Q ≤ 105
  • 1 ≤ x ≤ 106
  • Pentru întrebările de tip 3 și 4 se garantează că “x” există la momentul curent în mulțime.
  • Pentru 40 % dintre teste se garantează că Q ≤ 3000.
  • Se garantează că la final există elemente in mulțime.

Exemplu

interviu.in interviu.out Explicații
10
1 2
1 3
1 4
2 5
2 3
3 4
4 4
1 6
1 7
1 8
2
-1
2 4 6 7 8
Dupa primele 3 operații mulțimea va avea forma: [2, 3, 4].
Dupa cea de a 4-a operație nu se va întâmpla nimic, întrucât elementul 5 nu există. Ulterior, se va șterge elementul 3 si mulțimea va fi: [2, 4]. Așadar, răspunsurile la următoarele 2 întrebări sunt: 2 si -1.
In final, se vor adăuga elementele 6, 7, 8 in aceasta ordine, rezultând configurația finala a mulțimii.
10
1 10000
1 20000
1 30000
1 400000
1 500000
3 400000
4 20000
4 10000
2 20000
2 1
30000
30000
20000
10000 30000 400000 500000
Se vor insera cele 5 elemente, iar mulțimea va fi [10000, 20000, 30000, 400000, 500000]. Având în seama aceasta mulțime, vom răspunde la următoarele 3 întrebări ( Elementul de dinaintea lui 400000 este 30000, acesta fiind si elementul de dupa 20000. Elementul care se afla dupa 10000 este 20000 ). In final, vom șterge elementul 20000, neluând în seama ultima operație, întrucât elementul 1 nu exista.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii