| Fişierul intrare/ieşire: | mole.in, mole.out | Sursă | Lot Seniori Deva, 2019, baraj 1 |
| Autor | Andrei Constantinescu, Costin Oncescu | Adăugată de |  Tinca Matei •TincaMatei |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mole
Pentru a nu mai întâmpina probleme logistice, comisia lotului de pregătire de anul acesta a decis să stabilească clasamentul celor N participanţi independent de punctajele obţinute la cele două probe de concurs.
Din fericire pentru tine, însă, există o cârtiţă (eng. mole), a cărui nume nu îl vom menţiona, care ţi-a divulgat acest secret, astfel că ai aflat intenţiile malefice ale comisiei. Mai mult, persoana este dispusă să te ajute să descoperi clasamentul. Totuşi, pentru a nu fi descoperiţi, aţi hotărât să comunicaţi astfel:
- Vei întreba cârtiţa un posibil clasament p1, p2, ... , pN;
- Cârtiţa va porni de la clasamentul întrebat de tine şi îl va transforma în clasamentul comisiei, interschimbând pe rând locurile a câte doi participanţi. Să presupunem că numărul minim de schimbări este x. Cârtiţa îţi va răspunde întrebării cu x.
Interacţiune
Această problema este interactivă. Vi se pune la dispoziţie funcţia cu următorul cu următorul antet:
int ask(std::vector<int> guess);Atenţie! Această funcţie nu trebuie implementată de către voi. Graderul va implementa această funcţie. Argumentul guess reprezintă clasamentul de care veţi întreba. Funcţia va returna numărul minim de interschimbări x, descris mai sus. Argumentul guess trebuie să reprezinte o permutare validă a numerelor din intervalul [1, N]. În caz contrar, graderul va termina programul din execuţie şi va nota testul ca fiind incorect.
Detalii de implementare
Veţi implementa funcţia cu următorul antet:
std::vector<int> find_standings(int N);Funcţia find_standings va fi apelată o dată. N este numărul de concurenţi.
Funcţia trebuie să returneze, în final, clasamentul căutat. Pentru aceasta, din cadrul ei se poate apela de un număr limitat de ori funcţia de interacţiune ask (vezi secţiunea Punctare).
Din cauza limitărilor impuse de Infoarena şi pentru a reproduce condiţiile din concurs, recomandăm să foloseşti template-urile de aici .
Punctare
| Subtask | Punctaj | Constrângeri |
|---|---|---|
| 1 | 7 puncte | 3 ≤ N ≤ 6 Funcţia ask poate fi apelată de cel mult 1.000 ori. |
| 2 | 14 puncte | 3 ≤ N ≤ 100 Funcţia ask poate fi apelată de cel mult 5.000 ori. |
| 3 | 40 puncte | 3 ≤ N ≤ 200 Funcţia ask poate fi apelată de cel mult 4.000 ori. |
| 4 | 16 puncte | 3 ≤ N ≤ 200 Funcţia ask poate fi apelată de cel mult 2.700 ori. |
| 5 | 15 puncte | 3 ≤ N ≤ 200 Funcţia ask poate fi apelată de cel mult 1.800 ori. |
| 6 | 8 puncte | 3 ≤ N ≤ 200 Funcţia ask poate fi apelată de cel mult 1.600 ori. |
Exemplu
| Intrare | Ieşire |
|---|---|
| find_standings(3) | - |
| - | ask({1, 2, 3}) |
| 2 | - |
| - | ask({1, 3, 2}) |
| 1 | - |
| - | ask({2, 3, 1}) |
| 0 | - |
| - | return {2, 3, 1} |
| OK | - |
