OP

În urbea X au avut loc noi alegeri după ce Necromancerul a interferat cu buna desfășurare a primului tur. De data aceasta, $K$ candidați cu id-uri de la $1$ la $K$ au concurat în alegeri, $N+M$ cetățeni votând fiecare cu exact unul dintre candidați.

După ce a făcut curățenie exemplară în dosarele primăriei, Hetty a fost desemnată numărător unic oficial de voturi. Numărătoarea voturilor se face pe parcursul a două zile.

În prima zi, Hetty primește $N$ buletine de vot. După ce le procesează, ea trebuie să arhiveze cele $N$ buletine și nu se va mai atinge de ele. Pentru a nota rezultatele după prima zi de numărătoare, Hetty are dreptul să scrie într-un caiet un șir $B$ de $L$ biți.

În a doua zi, Hetty primește următoarele $M$ buletine de vot, dar și caietul în care și-a scris șirul $B$ de $L$ biți. Folosind informația notată în caiet, Hetty trebuie să spună, după fiecare buletin de vot procesat, care este candidatul câștigător luând în considerare toate cele $N$ voturi din prima zi, dar și voturile din a doua zi procesate până la momentul respectiv.

Cerință

Aveți de implementat două funcții (care trebuie să se regăsească în această ordine) care vor fi rulate separat, și nu puteți folosi memoria globală pentru a transmite informații între apelurile funcției. Prima funcție va simula acțiunile lui Hetty din prima zi, iar a doua funcție va simula acțiunile lui Hetty din a doua zi.

std::string code(int K, int N, std::vector<int> ids);

Pentru prima funcție, veți primi numărul $K$ de candidați, numărul $N$ de voturi din prima zi, și un vector cu $N$ numere (toate șirurile sunt indexate începând de la 0) reprezentând id-urile candidaților cu care au votat primii $N$ cetățeni și va trebui să returnați un șir de caractere binar B, de lungime $L$ aleasă de voi.

std::vector<int> decode(int K, int N, int M, std::string B, std::vector<int> ids);

Pentru a funcție, veți primi numărul $K$ de candidați, numărul $N$ de voturi din prima zi, numărul $M$ de voturi din a doua zi, șirul $B$ de $L$ biți și $M$ numere reprezentând id-urile candidaților cu care au votat cei $M$ cetățeni din a doua zi. Trebuie sa returnați un șir ce conține id-urile candidatului câștigător după fiecare nou vot procesat.

Restricții și precizări

• Un candidat câștigă dacă adună cele mai multe voturi dintre toți cei $K$ participanți.
• Dacă există mai mulți candidați cu același număr maxim de voturi, poate fi afișat oricare.
• Șirul de biți trebuie să conțină cel puțin un element.
• Veți primi puncte doar dacă această lungime $L$ se încadrează într-o limită superioară $L_{max}$ impusă.
• Pentru $10\%$ din teste, $1 \leq K \leq N \leq 10$, $M = 100$, $L_{max} = 1\ 000$
• Pentru alte $20\%$ din teste, $K = 500$, $N = 1\ 000$, $M = 1\ 000\ 000$, $L_{max} = 1\ 600$
• Pentru alte $20\%$ din teste, $K = 500$, $N = 1\ 000$, $M = 1\ 000\ 000$, $L_{max} = 1\ 400$
• Pentru alte $25\%$ din teste, $K = 250$, $N = 1\ 000$, $M = 1\ 000\ 000$, $L_{max} = 950$
• Pentru alte $25\%$ din teste, $K = 1\ 500$, $N = 5\ 000$, $M = 1\ 000\ 000$, $L_{max} = 5\ 100$
• Singurele declarații permise în program sunt: directivele #include, #define (doar pentru constante numerice), using și declarații de funcții. Nu se pot declara variabile globale, statice sau să se returneze pointeri.

Exemplu

Se apelează hint(3, 5, {1, 1, 1, 3, 3}) și se returnează 01010101.
Apoi, se apelează solve(3, 5, 7, 01010101, {3, 3, 2, 2, 2, 2, 2}) care va returna {1, 3, 3, 3, 3, 3, 2}.

Explicații

După primul vot procesat, candidații 1 și 3 sunt la egalitate, așa că putem afișa oricare.
După următoarul vot, doar candidatul 3 este în frunte, și rămâne acolo pentru încă 3 voturi procesate
După penultimul vot, candidații 2 și 3 sunt la egalitate așa că putem afișa oricare.
După ultimul vot procesat, doar candidatul 2 este în frunte.