decod

Serviciul Român de Informaţii (SRI) a dat de urma unei binecunoscute şi periculoase organizaţii teroriste, care îşi are sediul pe teritoriul ţării noastre. Folosind cei mai pricepuţi şi mai bine antrenaţi spioni şi ofiţeri, SRI a reuşit să identifice computerul principal al organizaţiei teroriste. Dacă va reuşi să acceseze informaţiile din acest computer, SRI îi va putea aresta pe toţi membrii organizaţiei şi va asigura (în continuare) pacea mondială. Singura problemă este spargerea codului de acces. Tot ceea ce se ştie despre acest cod este că el este reprezentat de către o permutare de lungime N. Specialiştii SRI au încercat diverse metode de a descoperi codul, însă tot ceea ce au reuşit să obţină este un program care, transmiţându-i-se ca parametru o permutare de lungime N, specifică în câte poziţii coincid această permutare şi codul de acces. Din păcate, şefii nu cred în utilitatea acestui program.

Cerinţă

Scrieţi un program care, folosind programul-ajutător (reprezentat sub forma unui modul), să determine codul de acces în computerul teroriştilor.

Protocol de interacțiune

Aveți de implementat următoarea funcție, unde N este lungimea permutării.

std::vector<int> solve(int N)

Programul dumneavoastră nu va citi date din vreun fişier de intrare. Acesta va apela numai funcţia

int check(std::vector<int> p) 

căreia îi va fi transmisă ca parametru, de fiecare dată, o permutare p de lungime N, indexată de la 0, cu elemente între 1 și N. Această funcţie va returna numărul de poziţii în care permutarea transmisă ca parametru coincide cu permutarea ce trebuie descoperită. Dacă p nu este o permutare validă, check va returna -1; altfel un număr între 0 și n. Programul dumneavoastră trebuie ca, după un număr finit de apelări ale funcţiei check, să descopere permutarea căutată. Complexitatea funcției va fi considerată O(n).

În final, funcția va returna o permutare de lungime N , indexată de la 0, cu elemente între 1 și N reprezentând răspunsul problemei.

Restricţii și precizări

• 5 ≤ N ≤ 650
• Fișierul "check.h" trebuie inclus
• Problema a fost modificată

Subtask 1 (10 puncte)

• 5 ≤ N ≤ 10

Subtask 2 (50 puncte)

• 5 ≤ N ≤ 500

Subtask 3 (40 puncte)

• 5 ≤ N ≤ 650

Exemplu

5
2 1 3 4 5

O serie posibilă de apeluri ale funcţiei check este următoarea:

• Se apelează funcţia check cu permutarea (1 2 3 4 5) şi este returnată valoarea 3
• Se apelează funcţia check cu permutarea (3 2 1 4 5) şi este returnată valoarea 2
• Se apelează funcţia check cu permutarea (2 1 3 4 5) şi este returnată valoarea 5

În final solve va returna permutarea (2 1 3 4 5)