enemies

Una dintre cele mai neînțelese relații dintre oameni este cea de dușmănie. La prima vedere pare a nu fi nicio regulă sau structură legată de aceste relații, doar legende și povești. De exemplu, faimoasa expresie “Dușmanul dușmanului meu este prietenul meu“ pare a fi doar o legendă și nimic mai mult.

O echipă de cercetători din Dorohoi crede că a reușit să inventeze un dispozitiv cu ajutorul căruia să poată studia aceste relații de dușmanie. Ei au la dispoziție $N$ cobai voluntari numerotați de la $0$ la $N - 1$. Aceștia au $M$ relații de dușmănie $X_i - Y_i$ ($X_i \neq Y_i , 0 \leq i \leq M - 1$) cu semnificația că persoana $X_i$ ($0 \leq X_i \leq N - 1)$ se află într-o relație de dușmănie cu persoana $Y_i$ ($0 \leq Y_i \leq N - 1$).

Dispozitivul este format dintr-o cameră în care pot intra o parte din acești $N$ oameni. Apoi acesta poate fi activat și după numeroase calcule, extrapolări și integrări va afișa pe un ecran numărul de relații de dușmănie între oamenii din cameră și cei aflați în exterior.

Cercetătorii trebuie să deducă toate relațiile de dușmănie fără să utilizeze dispozitivul de prea multe ori, altfel riscă ca unul din voluntari să îi considere dușmani și din aceasta cauză să nu mai poată să deducă relațiile. Voi trebuie să le spuneți cum să utilizeze dispozitivul de fiecare dată și la final să deduceți relațiile de dușmănie ale celor $N$ voluntari.

Detalii de implementare

Trebuie să implementați următoarea funcție:

std::vector<std::pair<int, int>> find_enemies(int N);

Funcția find_enemies va fi apelată exact o dată pentru fiecare test. $N$ va reprezenta numărul de oameni pentru care se caută relațiile de dușmănie. Funcția trebuie să întoarcă un vector de perechi reprezentând toate relațiile de dușmănie dintre cei $N$ oameni. Se acceptă orice soluție corectă astfel că cei doi indici din cadrul unei perechi, cât și perechile pot fi în orice ordine. Indicii oamenilor trebuie să fie valori întregi de la $0$ la $N - 1$. Puteți apela următoarea funcție în scopul găsirii acestor relații:

int split_people(std::string split);

Atenție! Această funcție nu trebuie implementată de către voi. Graderul va implementa această funcție. Argumentul $split$ trebuie să fie format din exact $N$ caractere care sunt fie $0$, fie $1$, în caz contrar graderul va termina programul din execuție și va nota testul ca fiind incorect. Funcția va întoarce câte relații de dușmănie sunt între oamenii din cameră și cei din exteriorul acesteia, oamenii fiind repartizați în funcție de caracterul corespunzător. Dacă $split_i = 0$ atunci al $i$-lea om va rămâne în afara camerei, iar dacă este $1$ al $i$-lea om va intra în camera dispozitivului.

Puteți apela această funcție de maxim $20 \ 000$ de ori, iar scorul vostru va fi calculat în funcție de acest număr (vezi secțiunea Punctare).

Punctare

Pentru orice test punctajul maxim se obține dacă funcția split_people este apelată de cel mult $10 \ 000$ de ori. Dacă numărul de apeluri ale acestei funcții în cadrul unui test este mai mare decât $10 \ 000$, dar mai mic sau egal cu $20 \ 000$ atunci punctajul obținut pe acel test este $75\%$ din punctajul asociat testului.

Punctajul pentru un subtask este minimul punctajelor obținute pe testele din acel subtask.

Atenție! Graderul oficial NU este adversarial. Asta înseamnă că relațiile de dușmănie sunt decise la începutul rulării graderului și nu depind de diferitele apeluri ale funcției split_people.

Model de grader

Atenție! Acest grader nu este neapărat cel folosit pentru evaluarea submisiilor.

Vi se pune la dispoziție un grader pentru a vă putea compila și testa codul local. Acesta va citi de la consolă datele de intrare în următorul format:

• linia $1$: $N \ M$, reprezentând numărul de oameni, respectiv numărul de relații de dușmănie.
• linia $2 + i$ ($0 \leq i \leq M - 1$): $X_i \ Y_i$, reprezentând perechi de oameni aflați în relație de dușmănie.

Dacă programul vostru întoarce corect relațiile de dușmănie folosind maxim $20 \ 000$ de apeluri ale funcției split_people atunci graderul va afișa Accepted: q, unde $q$ reprezintă numărul de apeluri ale funcției split_people.

Altfel, graderul va afișa în consolă Wrong Answer: MSG, unde $MSG$ poate avea una din următoarele valori și semnificații:

• invalid split: O valoare a lui $split$ dată ca parametru funcției split_people este invalidă. Mai exact, fie lungimea lui split nu este egală cu $N$, fie unul din caracterele din split nu este $0$ sau $1$.
• too many splits: Funcția split_people a fost apelată de mai mult de $20 \ 000$ de ori.
• answer size mismatch: Funcția find_enemies a întors un număr diferit de relații de dușmănie decât numărul corect.
• wrong guess: Funcția find_enemies a întors alte relații de dușmănie decât cele corecte.

De asemenea, graderul va scrie în fișierul enemies.txt toate relațiile de dușmănie întoarse de funcția find_enemies. Pe primul rând va afișa numărul de relații întoarse, apoi fiecare relație pe câte un rând, indicii oamenilor dintr-o relație fiind separați prin exact un spațiu.

Graderul și testele nu sunt cele din timpul concursului!

Exemplu

Să presupunem că $N = 4$, $M = 3$ și relațiile de dușmănie sunt $0 - 1$, $0 - 2$ și $1 - 3$. O succesiune de apeluri ale funcției split_people care determină aceste relații este următoarea:

Explicație

Pentru primul apel al funcției split_people, $0$ are exact $2$ relații de dușmănie, deci funcția va întoarce $2$.
Pentru cel de-al $4$-lea apel al funcției split_people toate cele $3$ relații de dușmănie sunt între un om din cameră și unul din afara acesteia.
Pentru cel de-al $6$-lea apel al funcției split_people numai relația de dușmănie $0 - 2$ va fi contorizată de dispozitiv.
În final, funcția find_enemies trebuie să întoarcă $[(3, 1), (0, 2), (0, 1)]$.