Ce problème est interactif.

Sur le comptoir de la pâtisserie des puces sont disposées deux rangées de gelées colorées à deux couches (la couche supérieure est $a$, la couche inférieure est $b$). En vertu de la règle de « complémentarité de la solidification » de la boutique, la somme des hauteurs des couches supérieure et inférieure de chaque gelée vaut exactement $n+1$. Les employés avaient initialement disposé chacune de ces deux rangées de façon que leurs hauteurs forment une permutation parfaite de $1 \sim n$, mais, la nuit dernière, un employé puce plein d'énergie a accidentellement inversé les couches supérieure et inférieure à certaines positions !

Le festival annuel des desserts va maintenant commencer, et les employés doivent retrouver la disposition initiale des gelées avant ces inversions (c'est-à-dire la suite $a$ des hauteurs de la couche supérieure avant les inversions).

Vous ne pouvez pas observer directement les hauteurs des gelées, mais vous pouvez donner des instructions à l'appareil de mesure automatique de la pâtisserie : indiquez plusieurs positions $i$, et l'appareil inversera les couches supérieure et inférieure à ces positions, puis renverra la différence entre les hauteurs maximale et minimale (l'étendue) de la couche supérieure actuelle, ainsi que celle de la couche inférieure. Attention : les effets de chaque inversion sont conservés.

Pouvez-vous retrouver la disposition initiale de la couche supérieure en effectuant un nombre limité de mesures avec inversions ?

La bibliothèque d'interaction choisit d'abord une permutation $p$ de $1\sim n$, puis construit la permutation $b_i=n+1-p_i$. Ensuite, pour chaque indice $i$, elle décide indépendamment d'échanger ou non les deux nombres à la position $i$. Les tableaux obtenus après ces échanges sont notés $a,b$. On a alors toujours $a_i+b_i=n+1$, mais $a,b$ ne sont pas nécessairement encore des permutations.

Vous connaissez $n$, mais pas ces deux tableaux. Vous pouvez choisir plusieurs positions et y échanger $a_i,b_i$ ; la bibliothèque d'interaction vous indiquera les étendues des deux tableaux après ces échanges. Les effets de chaque échange sont conservés.

Votre tâche consiste à retrouver le tableau $a$ avant la première requête. Une réponse est également considérée comme correcte si elle devient égale au tableau recherché après le remplacement simultané de chacune de ses valeurs $x$ par $n+1-x$.

Détails d'implémentation

Vous n'avez pas besoin d'implémenter la fonction main, et vous ne devez pas le faire.

Vous devez inclure le fichier d'en-tête range.h dans votre fichier source recover.cpp, et implémenter la fonction suivante :

std::vector<int> recover(int c, int n);

• $c$ est le numéro de la sous-tâche actuelle : il vaut $1,2,3,4$ dans les tests officiels et $0$ dans l'exemple. $n$ est la longueur des tableaux. La bibliothèque d'interaction appelle recover exactement une fois par test.
• La valeur renvoyée doit être un tableau d'entiers de longueur $n$ représentant $a$ avant la première requête, ou son complément global.

Vous pouvez appeler la fonction suivante :

std::pair<int, int> query(const std::vector<int>& positions);

• Les indices dans positions doivent être deux à deux distincts et appartenir à $[0,n-1]$. Il est permis de fournir un tableau vide.
• Pour chacun des indices dans positions, la bibliothèque d'interaction échange une fois les valeurs actuelles $a_i,b_i$, puis renvoie l'étendue de $a$ et celle de $b$ dans leur état actuel. Les échanges se cumulent d'une requête à l'autre, mais la réponse renvoyée doit retrouver le tableau initial, avant les échanges.
• L'étendue d'un tableau est définie comme sa valeur maximale moins sa valeur minimale. Puisque l'on a toujours $b_i=n+1-a_i$, les deux étendues sont nécessairement égales.
• Le nombre d'appels à query ne doit pas dépasser la limite $Q_{\max}$ du test en cours.

La bibliothèque d'interaction n'est pas adaptative : les tableaux initiaux sont fixés avant le début de recover et ne sont pas modifiés en fonction de vos requêtes. La bibliothèque utilisée pour l'évaluation finale peut différer de celle fournie pour les exemples. Votre programme ne doit ni lire les données internes de la bibliothèque d'interaction, ni utiliser directement les flux d'entrée et de sortie standard.

Test du programme

Placez recover.cpp, range.h et le fichier grader.cpp fourni en pièce jointe dans le même répertoire, puis compilez en C++17 :

g++ grader.cpp recover.cpp -o recover -O2 -std=c++17
./recover < ex_range1.in

La première ligne lue par la bibliothèque d'interaction locale contient $c,n,Q_{\max}$ ; la deuxième contient la permutation $p_0,\ldots,p_{n-1}$ ; la troisième contient $n$ nombres $0/1$, où $1$ indique qu'un échange est effectué à cette position avant le début de l'interaction. Seuls $c,n$ vous sont fournis comme paramètres de la fonction ; la permutation, les indicateurs d'échange et la limite du nombre de requêtes ne sont pas transmis directement à votre programme.

Si la réponse est correcte, la bibliothèque locale affiche Correct! sur la première ligne et Queries used: Q sur la deuxième, où $Q$ est le nombre de requêtes utilisées pendant cet appel. Si la réponse est incorrecte, elle affiche Wrong answer. ; si un appel à l'interface est invalide, elle indique également la cause de l'erreur sur le flux d'erreur standard.

Exemples

Entrée 1

0 6 67
3 1 6 4 2 5
0 1 1 0 1 0

Sortie 1

Correct!
Queries used: 16

Remarque

Dans cet exemple, avant le début de l'interaction, $a=(3,6,1,4,5,5)$ ; son complément global est $(4,1,6,3,2,2)$. Renvoyer l'un ou l'autre est correct. Le premier appel à query({}) renvoie $(5,5)$. La sortie ci-dessus correspond à l'exécution du programme de référence fourni en pièce jointe ; d'autres programmes corrects peuvent utiliser un nombre différent de requêtes.

Contraintes

Pour tous les tests, $1\le n\le 500$.

Le score de chaque sous-tâche est déterminé par le test dont le multiplicateur de score est le plus faible, comme décrit ci-dessous.

Sous-tâches

Si la réponse renvoyée par recover est incorrecte, si les paramètres de query sont invalides ou si le nombre de requêtes dépasse $Q_{\max}$, le score de ce test est $0$.

Sinon, pour les sous-tâches $1,2$, le test obtient la totalité des points. Pour les sous-tâches $3,4$, soit $Q$ le nombre de requêtes effectivement utilisées pour ce test ; le multiplicateur de score $f(Q)$ est calculé selon le tableau suivant :

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

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

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