« C'est un hors-la-loi et il est célèbre, Andrii Popa le courageux.

Jour et nuit il chevauche, Il prélève son tribut sur la grand-route Et partout dans le pays Les chasseurs de voleurs s'enfuient aussi vite qu'ils le peuvent »

— « Andrii Popa », Phoenix

Ghiță possède une séquence $S$ indexée à partir de $0$ composée de $N$ poids entiers strictement positifs. Comme il est le roi des Carpates, il souhaite construire un arbre binaire dont les nœuds portent les indices $0, 1, \ldots, N - 1$ tel que :

• Le parcours infixe (inorder) de l'arbre donne les nœuds par ordre croissant d'indices. Le parcours infixe d'un arbre binaire est formé du parcours infixe du sous-arbre enraciné au fils gauche de la racine (si ce fils existe), suivi de l'indice de la racine, suivi du parcours infixe du sous-arbre enraciné au fils droit de la racine (si ce fils existe).
• Si le nœud $x$ est le parent du nœud $y$, alors $S_x$ divise $S_y$.

Rappelons qu'un arbre binaire est une structure de données arborescente dans laquelle chaque nœud possède au plus deux fils, appelés fils gauche et fils droit.

Malheureusement, le célèbre hors-la-loi Andrii Popa a volé la séquence $S$, et Ghiță ne peut plus y accéder directement. À l'aide d'une technologie de pointe (son téléphone portable), il peut, pour deux sous-séquences contiguës quelconques $[a, b]$ et $[c, d]$ de $S$, savoir si $\gcd[a, b]$ est égal à $\gcd[c, d]$, où $\gcd[x, y]$ désigne le plus grand commun diviseur de $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$. Malheureusement, cette technologie est assez coûteuse — si Ghiță l'utilise plus de $Q$ fois, il devra payer une lourde amende. Aidez-le en utilisant cette technologie au plus $Q$ fois pour construire l'arbre souhaité. Il est garanti que cela est possible. Toute solution valide sera acceptée.

Interaction

Le candidat doit inclure l'en-tête popa.h (C / C++) ou implémenter popa.pas (Pascal). Le candidat doit implémenter la fonction suivante :

int solve(int N, int* Left, int* Right);

function solve(N: LongInt, var Left, Right: array of LongInt): LongInt;

Cette fonction doit renvoyer la racine de l'arbre, et affecter à $\text{Left}_i$ et $\text{Right}_i$ respectivement le fils gauche et le fils droit du nœud $i$. Si le nœud $i$ n'a pas de fils gauche, alors $\text{Left}_i$ doit valoir $-1$. Si le nœud $i$ n'a pas de fils droit, alors $\text{Right}_i$ doit valoir $-1$. Left et Right pointent vers deux tableaux de taille exactement $N$ qui ont déjà été alloués.

La fonction solve peut être appelée au plus $5$ fois au cours d'une même exécution. Nous conseillons de faire attention aux variables globales.

Le candidat peut utiliser la fonction suivante :

int query(int a, int b, int c, int d);

function query(a, b, c, d: LongInt): LongInt;

Cette fonction renvoie $1$ si et seulement si $\gcd[a, b]$ est égal à $\gcd[c, d]$, où $0 \le a \le b < N$ et $0 \le c \le d < N$, et $0$ sinon.

Sous-tâches

Sous-tâche 1 (37 points)

• $N = 100$
• $Q = 10000$

Sous-tâche 2 (24 points)

• $N = 1000$
• $Q = 20000$

Sous-tâche 3 (39 points)

• $N = 1000$
• $Q = 2000$

Exemples

Un exemple d'interaction pour $S = [12, 4, 16, 2, 2, 20]$ est :

Remarque

Un exemple d'arbre du type souhaité par Ghiță pour l'exemple précédent est :