GurgerBrill

,,Faci problema, nu faci problema, tot shaorma bagi după''

Se știu două lucruri despre cina festivă: faptul că se va servi shaorma și modul de așezare al invitaților. Vor fi $N$ persoane numerotate de la $1$ la $N$ și o cameră cu o masă rotundă care are exact $N$ locuri, iar fiecare persoană are un loc distinct rezervat ce nu este încă dezvăluit.

Pentru a descoperi locul rezervat fiecărei persoane se pot organiza $Q$ întâlniri ale celor $N$ invitați în sala de mese. Înainte de fiecare întâlnire poți stabili ordinea în care vor veni persoanele la aceasta. La finalul fiecărei întâlniri vi se dă lista invitaților care au ajuns la aceasta înaintea ambilor vecini din așezarea secretă de la masă.

Cerință

Să se afle locurile rezervate fiecărui invitat pe baza informațiilor obținute din cele $Q$ întâlniri.

Detalii de implementare

Trebuie să implementezi următoarea funcție

std::vector<int> find_places(int N);

Această funcție trebuie să returneze răspunsul, care reprezintă modul de așezare al invitaților la masă. Orice soluție în care fiecare din invitați au aceeași vecini ca în așezarea aleasă de comisie, va fi considerată corectă. Șirul întors de funcție este indexat de la $0$.

Poți folosi următoarea funcție în implementarea soluției tale.

std::vector<int> query(std::vector<int> order);

Această funcție va returna pentru întâlnirea stabilită (dată prin ordinea în care cele $N$ persoane ajung la întâlnire) un șir format din numerele de ordine ale persoanelor care au ajuns la întâlnire înaintea ambilor vecini din așezarea secretă de la masă.

Această funcție primește ca parametru indicii persoanelor în ordinea în care se așază la masă în cadrul unei întâlniri. Această funcție va întoarce șirul numerelor de ordine ale persoanelor care au ajuns la întâlnire înaintea ambilor vecini din așezarea secretă de la masă. Șirul dat ca parametru trebuie să fie o permutare a numerelor de la $1$ la $N$ și trebuie indexat de la $0$.

Nu uita să incluzi header-ul gurgerbrill.h!

Restricții

Interactorul nu este adaptiv. Permutarea nu se schimbă indiferent de întâlnirile pe care le stabilește concurentul.

Formulă de scoring

Fie $Q_{\text{conc}}$ numărul de interogări făcute de concurent. Fie $P$ punctajul asociat grupei de teste.

• Dacă $Q_{\text{conc}} \leq Q_{\text{min}}$, atunci se primesc $P$ puncte pe test.
• Dacă $Q_{\text{conc}} > Q_{\text{max}}$ atunci se primesc 0 puncte pe test.
• Altfel, scorul concurentului este $\displaystyle \frac{P}{3} \left( 1 + 2 \frac{Q_{\text{max}} - Q_{\text{conc}}}{Q_{\text{max}} - Q_{\text{min}}} \right)$

Exemplu

Se apelează find_places cu $N = 7$:
Concurent: $\text{query}(\{6, 1, 5, 7, 4, 3, 2\})$
Grader: $\{6, 5\}$
Concurent: $\text{query}(\{1, 5, 7, 4, 3, 2, 6\})$
Grader: $\{1, 5\}$
Concurent: $\text{query}(\{5, 7, 4, 3, 2, 6, 1\})$
Grader: $\{5, 4\}$
Concurent: $\text{query}(\{7, 4, 3, 2, 6, 1, 5\})$
Grader: $\{7, 4, 3\}$
Concurent: $\text{query}(\{4, 3, 2, 6, 1, 5, 7\})$
Grader: $\{4, 3\}$
Concurent: $\text{query}(\{3, 2, 6, 1, 5, 7, 4\})$
Grader: $\{3, 2\}$
Concurent: $\text{query}(\{2, 6, 1, 5, 7, 4, 3\})$
Grader: $\{2, 6, 5\}$
find_places returnează $\{1, 6, 3, 5, 7, 2, 4\}$