Fișierul intrare/ieșire | interviu.in, interviu.out | Sursă | ad-hoc |
---|---|---|---|
Autor | David Demetriad | Adăugată de | 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 |
Vezi soluțiile trimise | Statistici
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. |