La un supermarket există două case de marcat la care clienții își pot plăti cumpărăturile. Când intră în magazin, fiecare client primește un număr unic. Când aceștia vor să plătească, se așază la rând la una dintre cele două case. Clienții sunt procesați pe rând, în ordinea venirii lor.

Cerința

Scrieți un program care procesează cozile de la casele de marcat. Acest program primește N instrucțiuni pe care trebuie să le execute. Aceste instrucțiuni pot fi de următoarele 4 tipuri:

1 – S-a eliberat casa de marcat numărul 1. Trebuie afișat numărul clientului care urmează la rând; dacă nu este nimeni la coadă la casa respectivă, se va afișa -1.
2 – S-a eliberat casa de marcat numărul 2. Trebuie afișat numărul clientului care urmează la rând; dacă nu este nimeni la coadă la casa respectivă, se va afișa -1.
3 x – Clientul cu numărul x se așază la coadă la casa la care așteaptă mai puțini clienți; dacă la ambele case așteaptă același număr de clienți, atunci clientul cu numărul x se va așeza la coadă la casa 1; trebuie afișată coada la care se așază clientul x. Se garantează că acest client nu este deja așezat la vreun la rând.
4 x – Clientul cu numărul x părăsește rândul la care așteaptă (se garantează că era deja la un rând); în acest caz nu trebuie afișat nimic.

Date de intrare

Fișierul de intrare supermarket.in conţine pe prima linie numărul de instrucțiuni N. Pe fiecare dintre următoarele N linii se află câte o instrucțiune, în forma descrisă la cerinţă.

Date de ieșire

Fișierul de ieșire supermarket.out va conţine rezultatele afişate în urma executării instrucţiunilor din fişierul de intrare, în ordinea din fişier, câte un rezultat pe o linie.

Restricții și precizări

4 ≤ N ≤ 100.000
1 ≤ x ≤ 1.000.000
Pentru teste valorând 30 de puncte, 4 ≤ N ≤ 1.000
Pentru teste valorând 30 de puncte nu vor exista instrucțiuni de tipul 4.
Un client care a părăsit la un moment dat rândul (fie în urma unei instrucțiuni de tipul 4, fie datorită faptului că a plătit la casă), se poate întoarce și se poate așeza din nou rând (ca și cum ar fi venit prima dată).

Exemplu

supermarket.in

supermarket.out

Explicație

Clientul 5 se aşază la rând la casa 1
Clientul 21 se aşază la rând la casa 2
Clientul 7 se aşază la rând la casa 1
La casa 2 intră clientul 21
La casa 1 intră clientul 5
La casa 2 nu este nimeni în așteptare
Clientul 5 se aşază la rând la casa 2
Clientul 8 se aşază la rând la casa 1
Clientul 7 părăseşte rândul (nu se afişează nimic)
La casa 1 intră clientul 8

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema supermarket:

#include <bits/stdc++.h>
#define st first
#define nd second

using namespace std;

const int N = 1000100;
int n, k, m, op, x;
int t[N], sz[3], where[N];

queue <pair<int, int> > q[3];

int main() {

    freopen("supermarket.in", "r", stdin);
    freopen("supermarket.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin >> n;

    assert(n <= 100000);

    for(int i = 1; i <= n; i++) {

        cin >> op;

        assert(op >= 1 && op <= 4);

        if(op <= 2) {
            while(!q[op].empty() && t[q[op].front().st] != q[op].front().nd)
                q[op].pop();

            if(q[op].empty()) {
                cout << "-1\n";
                continue;
            }

            t[q[op].front().st] = -1; // este scos din coada
            where[q[op].front().st] = 0;
            cout << q[op].front().st << '\n';
            q[op].pop();
            sz[op]--;
        } else if(op == 3) {

            cin >> x;
            assert(1 <= x && x <= 1e6);

            assert(where[x] == 0);

            int sw = 1;
            if(sz[1] > sz[2]) sw = 2;

            sz[sw]++;
            t[x] = i;
            q[sw].push({x, i});
            where[x] = sw;

            cout << sw << '\n';

        } else {
            cin >> x;
            assert(1 <= x && x <= 1e6);
            assert(where[x] <= 2 && where[x] > 0);

            sz[where[x]]--;
            where[x] = 0;
            t[x] = -1; // il scot din coada
        }
    }
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2895 supermarket

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2895 supermarket de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2895 supermarket