P9507 [BalkanOI 2018] Popa

Translated from BalkanOI 2018 Day 2 T2 “Popa”. > *"He's an outlaw and he's famous* > *Andrii Popa the courageous.* > *Day and night he rides,* > *He takes his tribute from the main road* > *And everywhere in the country* > *The thief catchers are running away as fast as they can"* > > *\- ["Andrii Popa", Phoenix](https://music.163.com/song?id=508736536)*

Ghiță has a sequence $S$ of positive integers indexed from $0$. Since he is the King of the Carpathians, he wants to construct a binary tree with nodes numbered $0,1,\ldots,N-1$ such that: - The inorder traversal of the tree lists the node indices in increasing order. The inorder traversal of a binary tree is the concatenation, in order, of the inorder traversal of the subtree rooted at the left child of the root (if it exists), the index of the root, and the inorder traversal of the subtree rooted at the right child of the root (if it exists). - If $x$ is the parent of node $y$, then $S_x$ divides $S_y$. A binary tree is a tree structure where each node has at most two children, called the left child and the right child. Unfortunately, the famous outlaw Andrii Popa stole the sequence $S$, so Ghiță cannot access it directly. However, for any two contiguous subarrays $[a,b]$ and $[c,d]$, he can use the most advanced technology (his phone) to determine whether $\gcd[a,b]$ is equal to $\gcd[c,d]$, where $\gcd[x,y]$ denotes the greatest common divisor of $S_x,S_{x+1},S_{x+2},\ldots,S_y$. Unfortunately, this technology is very expensive—if Ghiță uses it more than $Q$ times, he will have to pay a huge fine. Please help him construct the desired tree using this technology at most $Q$ times. It is guaranteed that this is possible. Any valid construction will be accepted. ### Interaction This problem only supports interactive solutions via functions in C++. The contestant’s code does not need to and must not include `popa.h`. You need to implement the following function: ```cpp int solve(int N, int* Left, int* Right); ``` The function must return the root of the tree, and set `Left[i]` and `Right[i]` to be the left child and the right child of node $i$, respectively. If node $i$ has no left child, then `Left[i]` should be set to $-1$. If node $i$ has no right child, then `Right[i]` should be set to $-1$. `Left` and `Right` point to two already-allocated arrays of length exactly $N$. The function `solve` will be called at most $5$ times in a single run. We suggest using global variables carefully. You may call the following function (note that you must declare this function in your code): ```cpp int query(int a, int b, int c, int d); ``` This function returns $1$ if and only if $\gcd[a,b]=\gcd[c,d]$, where $0\le a\le b

See “Interaction”.

See “Interaction”.

### Constraints | Subtask ID | Limits | Score | | :----------: | :----------: | :----------: | | $1$ | $N=100,Q=10^4$ | $37$ | | $2$ | $N=10^3,Q=2\times 10^4$ | $24$ | | $3$ | $N=10^3,Q=2\times 10^3$ | $39$ | Translated by ChatGPT 5