Après plusieurs centaines d'années, la ville de JOI est tombée en ruines. IOI-chan, une exploratrice, explore maintenant l'endroit où se trouvait la bibliothèque. Ses recherches ont permis d'établir les faits suivants :

• La bibliothèque de JOI possédait une étagère horizontale comportant $N$ emplacements alignés pour ranger des livres, numérotés de $0$ à $N-1$ de gauche à droite. Chaque emplacement pouvait accueillir exactement un livre.
• Il y avait $N$ livres sur l'étagère, numérotés de $0$ à $N-1$.
• Un agencement des livres est une façon de placer les $N$ livres dans les $N$ emplacements.
• Il existait un agencement correct des livres : dans cet agencement, le livre $B_i$ ($0\le i\le N-1$) se trouvait à l'emplacement $i$. Tous les $B_i$ étaient distincts.

L'agencement des livres changeait souvent. Nous savons que, dans cette bibliothèque, on remettait les livres dans l'agencement correct en répétant l'opération suivante.

Opération : soit $x$ le livre le plus à gauche parmi ceux dont l'emplacement diffère de celui de l'agencement correct. Soit également $y$ le livre qui occupe actuellement l'emplacement où le livre $x$ doit se trouver dans l'agencement correct. Échanger les emplacements des livres $x$ et $y$.

Bien qu'IOI-chan ait retrouvé les anciens livres de la bibliothèque, elle n'a pas pu déterminer leur agencement correct. Elle a cependant découvert une vieille machine qui gérait les opérations de l'étagère. Si l'on spécifie un agencement des $N$ livres et que l'on envoie une requête à la machine, celle-ci renvoie le nombre d'opérations nécessaires pour remettre tous les livres dans l'agencement correct. IOI-chan veut découvrir cet agencement en interrogeant la machine. Comme celle-ci est ancienne, elle peut lui envoyer au plus $5\,000$ requêtes.

Écrivez un programme qui, à partir des informations sur l'étagère, détermine l'agencement correct des livres en envoyant au plus $5\,000$ requêtes.

Détails d'implémentation

Vous devez soumettre un fichier.

Il s'agit de library3.cpp. Il doit implémenter la fonction suivante. Le programme doit inclure library3.h avec la directive de prétraitement #include.

• void solve(int N)

  Cette fonction est appelée une seule fois par cas de test.

  • Le paramètre N est le nombre $N$ de livres.

Dans library3.cpp, vous pouvez appeler les fonctions suivantes.

• int query(const std::vector<int> a)

  Cette fonction permet à IOI-chan d'envoyer une requête à la machine.

  • Le paramètre a est un tableau de longueur $N$ indiquant l'agencement des $N$ livres spécifié dans la requête. Dans cet agencement, le livre a[i] ($0\le i\le N-1$) doit occuper l'emplacement $i$.
  • La valeur de retour est le nombre d'opérations nécessaires pour remettre tous les livres dans l'agencement correct, en partant de l'agencement spécifié.
  • La longueur du paramètre a doit être $N$. Sinon, votre programme reçoit le verdict Wrong Answer [1].
  • Chaque élément du paramètre a doit être compris entre $0$ et $N-1$. Sinon, votre programme reçoit le verdict Wrong Answer [2].
  • Chaque élément du paramètre a doit être distinct de tous les autres. Sinon, votre programme reçoit le verdict Wrong Answer [3].
  • Vous ne devez pas appeler query strictement plus de $5\,000$ fois. Si elle est appelée plus de $5\,000$ fois, votre programme reçoit le verdict Wrong Answer [4].

• void answer(std::vector<int> b)

  Votre programme indique l'agencement correct des livres en appelant cette fonction.

  • Le paramètre b est un tableau de longueur $N$ indiquant l'agencement des $N$ livres proposé dans la réponse. Dans cet agencement, le livre b[i] ($0\le i\le N-1$) doit occuper l'emplacement $i$.
  • La longueur du paramètre b doit être $N$. Sinon, votre programme reçoit le verdict Wrong Answer [5].
  • Chaque élément du paramètre b doit être compris entre $0$ et $N-1$. Sinon, votre programme reçoit le verdict Wrong Answer [6].
  • Chaque élément du paramètre b doit être distinct de tous les autres. Sinon, votre programme reçoit le verdict Wrong Answer [7].
  • L'agencement proposé doit être l'agencement correct. Sinon, votre programme reçoit le verdict Wrong Answer [8].
  • La fonction answer doit être appelée exactement une fois. Si elle est appelée plus d'une fois, votre programme reçoit le verdict Wrong Answer [9]. À la fin de solve, si answer n'a pas été appelée, votre programme reçoit le verdict Wrong Answer [10].

Remarques importantes

• Votre programme peut implémenter d'autres fonctions pour un usage interne ou utiliser des variables globales.
• Votre programme ne doit utiliser ni l'entrée standard ni la sortie standard. Il ne doit communiquer avec d'autres fichiers par aucun moyen. Il peut cependant écrire des informations de débogage sur la sortie d'erreur standard.

Compilation et exécution de test

Vous pouvez télécharger depuis la page du concours une archive contenant un évaluateur d'exemple pour tester votre programme. L'archive contient également un exemple de code source de votre programme.

L'évaluateur d'exemple est le fichier grader.cpp. Pour tester votre programme, placez grader.cpp, library3.cpp, library3.h dans le même répertoire et exécutez la commande suivante pour compiler vos programmes. Vous pouvez aussi exécuter compile.sh, présent dans l'archive.

g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp

Si la compilation réussit, le fichier exécutable grader est créé.

L'évaluateur réel diffère de l'évaluateur d'exemple. Ce dernier s'exécute dans un seul processus, lit les données sur l'entrée standard et écrit les résultats sur la sortie standard.

Entrée de l'évaluateur d'exemple

L'évaluateur d'exemple lit les données suivantes sur l'entrée standard.

$$ \begin{array}{llll} N\\ B_0&B_1&\cdots&B_{N-1} \end{array} $$

$B_i$ ($0\le i\le N-1$) est le numéro du livre occupant l'emplacement $i$ dans l'agencement correct.

Sortie de l'évaluateur d'exemple

L'évaluateur d'exemple écrit les informations suivantes sur la sortie standard et la sortie d'erreur standard (les guillemets sont donnés pour plus de clarté).

• Si votre programme est jugé correct, il indique le nombre d'appels à query, par exemple Accepted: 3000.
• Si votre programme reçoit un verdict Wrong Answer, l'évaluateur d'exemple en indique le type, par exemple Wrong Answer [3].

Si votre programme satisfait les conditions de plusieurs types de Wrong Answer, l'évaluateur d'exemple n'en signale qu'un seul.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

• $2\le N\le 500$.
• $0\le B_i\le N-1$ ($0\le i\le N-1$).
• $B_i\ne B_j$ ($0\le i<j\le N-1$).
• Toutes les valeurs données sont des entiers.

Sous-tâches

1. (2 points) $N\le 6$.
2. (19 points) $N\le 100$.
3. (79 points) Aucune contrainte supplémentaire.

Exemple d'interaction

Voici une entrée d'exemple pour l'évaluateur d'exemple et les appels de fonctions correspondants.

Entrée 1

4
2 0 3 1

Exemples d'appels de fonctions

Remarque

Par exemple, l'appel query([0, 1, 2, 3]) spécifie l'agencement dans lequel les livres 0, 1, 2, 3 occupent respectivement les emplacements 0, 1, 2, 3. L'opération est répétée comme suit.

1. Échanger les emplacements des livres 0 et 1. Les livres 1, 0, 2, 3 occupent respectivement les emplacements 0, 1, 2, 3.
2. Échanger les emplacements des livres 1 et 3. Les livres 3, 0, 2, 1 occupent respectivement les emplacements 0, 1, 2, 3.
3. Échanger les emplacements des livres 3 et 2. Les livres 2, 0, 3, 1 occupent respectivement les emplacements 0, 1, 2, 3.

Comme il faut 3 opérations pour remettre tous les livres dans l'agencement correct, la valeur de retour est 3.

Cette entrée d'exemple satisfait les contraintes de toutes les sous-tâches.