PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:MEDIUM PREREQUISITES:Divide and conquer PROBLEM:Given an unknown permutation $A$ of numbers from $1$ to $N$, ask queries of form: $\texttt{divisible}(x, y, d) := \texttt{true}$ if and only if $A_x  A_y$ is divisible by $d$ and find out what the permutation is exactly. The hard part of the problem is the fact that you can ask at most $13 \cdot N$ $\texttt{divisible}$ queries and at most $N1$ $\texttt{less}$ queries. QUICK EXPLANATION:Use divide and conquer and recursion to solve the problem. While there are more than $2$ elements in the instance of a problem, partition them into two almost equal sets using $\texttt{divisible}$ query. Solve the problem for both partitions recursively and merge these subresults using the less query. EXPLANATION:In subtasks $1, 2$ and $3$ the constrains are low enough to allow multiple different approaches. In particular they allow more calls to the $\texttt{divisible}$ query. The general idea behind some of them is also covered in the explanation of the intended solution, so we recommend to read the below detailed explanation of this method. In the last subtask, the permutation is quite large  it has up to $10^4$ elements. We are going to solve the problem recursively using divide and conquer approach. Notice that when the instance of the problem is very small, i.e. $N \leq 2$, the problem is very easy to solve. In particular, when $N=1$ there is nothing to do, because the partition is already known, and if $N = 2$ then, one $\texttt{less}$ query is enough to determine the permutation. So the question is what to do when $N > 2$? Well, we can use $\texttt{divisible}$ query then. The idea is that we want to partition the initial indices of the permutation into two almost equal in size groups, solve the problem recursively for the partitions and finally somehow combine these result into the final result. Let $solve(indices, divisor)$ be a recursive function finding out the absolute order of elements of the permutation with indices belonging to $\texttt{indices}$ array and using $divisor$ as the value for $d$ in $\texttt{divisible}$ query to partition the elements. Moreover, the $solve$ function will return the index of the smallest number in the permutation with index in indices  we will be using this element to merge two subproblems solved recursively. The final answer to the problem will be the partition returned by calling $solve([1,2,\ldots,N], 2)$. If there are no more than $2$ indices we know what to do, otherwise we are going to partition indices into two groups $P_1$ and $P_2$ as follows:
The above method partition the indices into two almost equal in size sets. For example, let’s assume that the initial permutation is $5,3,2,4,1$ and we are solving the problem for all the indices $1,2, \ldots, 5$. Then the partition will assign indices as follows: $P_1 = \{1, 2, 5\}$ The index $1$ is in $P_1$ because it is the first element of $\texttt{indices}$. The indices $2$ and $5$ are also in $P_1$ because the results of $\texttt{divisible(1, 2, 2)}$ and $\texttt{divisible(1, 5, 2)}$ are true (for example $53$ is divisible by $2$). Other elements are in $P_2$ because the result of $\texttt{divisible}$ query for them is $\texttt{false}$. After the partition, we are going to solve the problems corresponding to the indices in $P_1$ and $P_2$ separately with $divisor$ multiplied by two, so we will call two functions:
We multiply the divisor by $2$ to allow the partitions performed during these subcalls to be done in the same way. By the definition, these functions returns the absolute orders of the elements in the permutation with indices in $P_1$ and with indices in $P_2$. The only thing left to do is to merge these two orders into the final order. Let $s_1$ be the index of the smallest element in the permutation among elements with indices in $P_1$. Similarly, let $s_2$ be the index of the smallest element in the permutation among elements with indices in $P_2$. These elements are also returned from recursive calls. We are going to use them to merge subresults into the final result. Notice that if $s_1 < s_2$, then the smallest element, i.e. the element with value $1$ is among the element with indices in $P_1$. Moreover, the $3$rd smallest, $5$th smallest, ... elements among all elements with indices in $\texttt{indices}$ have also indices in $P_1$ and all other elements have indices in $P_2$. In the other case, if $s_2 < s_1$ the situation is opposite and the elements with ranks $1, 3, 5, \ldots$ have indices in $P_2$ and all other elements have indices in $P_1$. Thus calling a query $less(s_1, s_2)$ allows us to determine how to merge the absolute orders of element with indices in $P_1$ and $P_2$ into one absolute order of elements with indices in $P_1 \bigcup P_2$. Notice that this method calls $\texttt{divisible}$ query at most $13 \cdot N$ times because it calls it no more than $N$ times on each level of recursion tree besides two deeper ones and the recursion tree has depth non greater than $\log N = 14$. Also, this methods calls $\texttt{less}$ query at most $N1$ times, from the same reason. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 29 Oct '16, 21:50

Can anyone tell me Why I am getting TLE even for subtask 1 and 2? answered 31 Oct '16, 23:15
You have to flush stdout after you have written something to it. Alternatively you could flush it right before reading something from stdin.
(02 Nov '16, 15:37)
@ceilks flushed stdout every time I wrote something to it, still getting TLE.
(27 Nov '16, 16:23)

Why would elements with rank 1, 3, 5, .. would be in one of the result vectors? answered 02 Nov '16, 11:22

And I also did not understand this part of the Editorialist's solution.
answered 02 Nov '16, 12:48
