Fișierul intrare/ieșire | lacoada.in, lacoada.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 0.7 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
La coadă
La BIG au băgat pui1. Instantaneu s-a format o coadă de N persoane, numerotate în ordine de la 1 la N. La coadă se pot întâmpla următoarele lucruri:
- Servire: prima persoană de la coadă primește un pui și pleacă acasă.
- Sosire: la coadă se mai așează o persoană. Noii veniți sunt numerotați în continuare: N + 1, N + 2 ș.a.m.d.
- Îmbrâncire(x): persoana numărul x face rost de o relație și se îmbrâncește până pe prima poziție a cozii. Dacă persoana era deja prima, nu se schimbă nimic.
Se dă o listă de K operații. Să se spună care este configurația finală a cozii. Se garantează că în niciun moment lungimea cozii nu va depăși N (oamenii se descurajează dacă văd o coadă prea lungă și nu se mai așează). Se garantează că operațiile de servire și îmbrâncire nu se vor efectua pe o coadă goală.
Date de intrare
Fișierul de intrare lacoada.in conține pe prima linie numerele N și K. Pe următoarele K linii se vor găsi operațiile, numerotate ca mai sus, într-una din formele
1
2
3 x
Se garantează că x este numărul unei persoane din coadă.
Date de ieșire
În fișierul de ieșire lacoada.out se va tipări pe prima linie lungimea cozii la sfârșitul operațiilor. Pe a doua linie se vor tipări, în ordine, numerele persoanelor de la coadă, începând cu prima.
Restricții
- 1 ≤ N ≤ 60.000
- 1 ≤ K ≤ 1.000.000
Exemplu
lacoada.in | lacoada.out | Explicație |
---|---|---|
6 6 3 5 1 3 3 2 3 7 1 |
5 3 1 2 4 6 |
5 se îmbrâncește, coada devine 5 1 2 3 4 6 5 este servit, coada devine 1 2 3 4 6 3 se îmbrâncește, coada devine 3 1 2 4 6 7 sosește, coada devine 3 1 2 4 6 7 7 se îmbrâncește, coada devine 7 3 1 2 4 6 7 este servit, coada devine 3 1 2 4 6 |
Note
1 Spre norocul vostru, nu este nevoie să știți ce este un BIG sau cine „au băgat” pui.