Ce problème est interactif.

À la veille de l'ouverture du festival des desserts, le chef peaufine avec soin la création emblématique de sa boutique : « 千层幻彩慕斯 ». Ce dessert est composé de $n$ morceaux de mousse aux saveurs différentes, numérotés $0,1,\dots,n-1$.

Cependant, dans la précipitation, son assistant a accidentellement mélangé l'ordre des morceaux de mousse. Ils sont désormais alignés de gauche à droite selon une permutation inconnue $p=(p_0,p_1,\dots,p_{n-1})$, où $p_i$ désigne le numéro du morceau de mousse placé à la position $i$.

Pour déterminer la position exacte de chaque morceau de mousse, vous pouvez utiliser un appareil de test des desserts. Chaque fois que vous choisissez trois positions deux à deux distinctes $x,y,z$, l'appareil vous renvoie la somme du plus petit et du plus grand numéro parmi ces trois morceaux de mousse :

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

La cloche annonçant l'ouverture va bientôt sonner. Parviendrez-vous à retrouver exactement la position de chaque morceau de mousse à l'aide d'un nombre limité de tests ?

On considère une permutation de longueur $n$, notée $p$, dont les éléments sont exactement $0,1,\ldots,n-1$. Vous ne connaissez pas le contenu de $p$.

Vous pouvez choisir trois indices deux à deux distincts $x,y,z$ ; la bibliothèque d'interaction renvoie alors

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

Votre tâche est de reconstituer la permutation entière. La limite du nombre de requêtes et la méthode de calcul du score en fonction de ce nombre sont précisées ci-dessous.

Détails d'implémentation

Vous n'avez pas besoin d'implémenter la fonction main et ne devez pas le faire. Le fichier source soumis doit contenir :

#include "mousse.h"

Vous devez implémenter les deux fonctions suivantes :

void init(int c);
std::vector<int> mousse(int c, int n);

• $c$ est le numéro de la sous-tâche ; $c=0$ désigne l'exemple. Chaque cas de test contient exactement une instance. Pour ce cas de test, la bibliothèque d'interaction appelle une fois init(c), puis une fois mousse(c,n).
• mousse doit renvoyer un tableau de longueur $n$ dont l'élément d'indice $i$ est $p_i$, les indices commençant à $0$.

Vous pouvez appeler la fonction suivante pour effectuer une requête :

int query(int x, int y, int z);

Il faut que $0\le x,y,z < n$ et que $x,y,z$ soient deux à deux distincts. La fonction renvoie $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$.

Test de votre programme

Les pièces jointes contiennent mousse.h, la bibliothèque d'interaction locale grader.cpp et un programme d'exemple template_mousse.cpp. Enregistrez votre programme dans mousse.cpp, puis vous pouvez exécuter les commandes suivantes dans le répertoire de ce problème :

g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.in

La bibliothèque d'interaction locale lit la permutation cachée sur l'entrée standard ; votre programme ne doit pas lire lui-même ces données. Le format d'entrée est le suivant :

• La première ligne contient deux entiers $c,n$.
• La deuxième ligne contient $p_0,p_1,\ldots,p_{n-1}$.

Si la réponse est correcte, la bibliothèque d'interaction affiche Correct! et Max queries used: Q, où $Q$ est le nombre de requêtes effectuées pour ce cas de test ; si la réponse est incorrecte, elle affiche Wrong answer.. En cas de requête invalide ou de dépassement de la limite du nombre de requêtes, le programme affiche un message d'erreur sur la sortie d'erreur standard et se termine. Vous pouvez ajouter l'option -v pour consulter le nombre de requêtes effectuées pour ce cas de test.

Exemples

Entrée 1

0 10
0 2 9 1 5 8 3 7 6 4

Sortie 1

Correct!
Max queries used: 15

Remarque

Par exemple, lors d'un appel à query(0,1,2), les trois valeurs correspondantes sont $0,2,9$ et la valeur renvoyée est $0+9=9$. Le programme de référence effectue $15$ requêtes sur cette instance. Ce nombre peut être différent si vous utilisez une autre stratégie.

Contraintes

Pour toutes les données de test, $n\in\{10,100,10^5\}$ et $p$ est une permutation de $0\sim n-1$. Chaque cas de test contient exactement une instance.

Pour l'exemple, $c=0$ et $n=10$, et la limite du nombre de requêtes est $1000$.

Sous-tâches

Remarques :

• La bibliothèque d'interaction n'est pas adaptative. La permutation de chaque cas de test est fixée avant l'appel à votre programme et ne change pas en fonction des requêtes.
• Vous ne devez pas obtenir la permutation cachée en lisant l'entrée standard ou par d'autres moyens non autorisés. L'implémentation de la bibliothèque d'interaction utilisée pour l'évaluation finale peut différer de celle de la bibliothèque locale.

Si, pour un cas de test, mousse renvoie une réponse incorrecte, les arguments de query sont invalides, ou le nombre de requêtes dépasse $Q_{\max}$ pour la sous-tâche correspondante, le multiplicateur de score de ce cas de test est $0$.

Pour les sous-tâches $1,2$, vous obtenez tous les points de la sous-tâche uniquement si les réponses à tous ses cas de test sont correctes.

Pour les sous-tâches $3,4$, si le multiplicateur de score d'un seul cas de test est $0$, le score de la sous-tâche est $0$. Sinon, soit $Q$ le nombre maximal de requêtes parmi tous les cas de test de cette sous-tâche. Le multiplicateur de score $f(Q)$ est déterminé par le tableau suivant :

Si $Q\le 99970$, alors $f(Q)=100\%$. Si $Q$ se situe entre deux lignes consécutives $(Q_i,f_i)$ et $(Q_{i+1},f_{i+1})$ du tableau, alors :

$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$

Le score de la sous-tâche $3$ est $30f(Q)$ et celui de la sous-tâche $4$ est $60f(Q)$. Le score final est arrondi à $3$ chiffres après la virgule.

Limite de temps : $10\ \mathrm{s}$.

Limite de mémoire : $512\ \mathrm{MiB}$.