|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||0||0||0||0.000%|
“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
Ghiță has a 0-indexed sequence S of N positive integer weights. Since he is the king of the Carpathians, he wants to construct a binary tree whose nodes have indices 0, 1, …, N - 1 such that:
We recall that a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
Unfortunately, the famous outlaw Andrii Popa has stolen the sequence S, and Ghiță can no longer access it directly. Using advanced technology (his mobile phone), he can, for any two continuous subsequence [a, b] and [c, d] of S, find out whether gcd[a, b] equals gcd[c, d], where gcd[x, y] is the greatest common divisor of Sx, Sx+1, Sx+2, …, Sy. Unfortunately, the technology is quite expensive – if Ghiță uses it more than Q times, he will have to pay a large fine. Help him by using the technology at most Q times to build the desired tree. It is guaranteed that this is possible. Any valid solution will be accepted.
The contestant should include the header
popa.h (C / C++) or implement
popa.pas (Pascal). The contestant needs to implement the following function:
int solve(int N, int* Left, int* Right); function solve(N: LongInt, var Left, Right: array of LongInt): LongInt;
This function should return the root of the tree, and set
Righti to the left and right children of the node
i respectively. If node
i doesn’t have a left child, then
Lefti should be -1. If node
i doesn’t have a right child, then
Righti should be -1.
Right point to two arrays of sizes exactly N that have already been allocated.