sorting

Sashka regularly takes part in online programming competitions. The prize for the current one is participation in a summer programming camp in the Maldives. Specially for this contest she has set her username to be Sorting. One of the tasks is the following:
The jury has come up with a permutation $p_1,p_2,p_3,\ldots,p_N$ of the numbers from 1 to N. The task is to find the permutation and in order to do so you can ask the jury the following two types of questions:

1. Given two positions x and y in the permutation $(1\le x,y\le N)$, is it true that $p_x < p_y$?
2. Given a number d and two positions x and y in the permutation $(1\le x,y,d\le N)$, is it true that $|p_x-p_y\ |\equiv0\ (mod\ d)$. In other words, is it true that the difference of the elements in the permutation at the x-th and y-th positions is divisible by d?

You have to ask as few questions as possible from the first type (see the scoring section below), but the number of questions of the second type is unlimited.

Task

Help Sashka by writing a program sorting, which by given N restores the permutation. It must contain the function solve, which will be compiled and executed with a jury’s program.

Implementation details

The solve function must have the following prototype:

std::vector <int> solve(int N);

The function will be called with one parameter N, equal to the number of elements in the permutation. The function should return a vector with N different elements – the permutation your program has found.

The compare and divisible functions are provided for questions to the jury.

The compare function must have the following prototype:

bool compare(int x, int y);

The function will return true, if $p_x < p_y$ and false otherwise.

The divisible function must have the following prototype:

bool divisible(int x, int y, int d);

The function will return true, if $\left|p_x-p_y\right|\equiv0\ (mod\ d)$ and false otherwise.

If you call the functions with invalid parameters, your program will be terminated and you will receive Wrong Answer.

Your code must contain the solve function. It may contain other code and functions necessary for your work, but it must not contain the main function. Also, you must not read from the standard input or print to the standard output. Your program must also include the sorting.h header file by instruction to the preprocessor:

#include "sorting.h"

Constraints

• $2\le N\le500\ 000$
• $1\le p_i\le N$ for each $1\le i\le N$.
• $p_i\neq p_j$ for each $1\le i < j\le N$.

Scoring

• In tests worth 20% of the points: $N\le500$
• In tests worth 30% of the points: $N\le2000$
• In tests worth 40% of the points: $N\le10\ 000$
• In tests worth 60% of the points: $N\le75\ 000$
• In tests worth 100% of the points: $N\le500\ 000$
• If you have guessed the permutation incorrectly, you will receive 0% of the points for that test. Otherwise, let you have asked Q questions from the first type. Then the value of the variable P is defined as follows:
  • If $0\le Q\le\frac{N}{2}$, P=1.00.
  • If $\frac{N}{2} < Q\le N$, P=0.70.
  • If $N < Q\le2N$, P=0.50.
  • If $2N < Q\le N\left\lceil{log}_2N\right\rceil$, P=0.15.
  • If $N\left\lceil{log}_2N\right\rceil < Q\le N(1+\left\lceil{log}_2N\right\rceil)$, P=0.10.
  • If $N\left(1+\left\lceil{log}_2N\right\rceil\right) < Q$, P=0.05.

Then the points which you will receive for the test are equal to: $(points\_for\_the\_test)\times P$.

Local testing

For local testing you are provided with the files sorting.h and _grader.cpp. Place your file sorting.cpp and the two provided files in the same folder. Then compile the three files together. In such a way, you will make a program to check the correctness of your solution. The program will require the following sequence of data:

• on the first line: one positive integer – the number of elements in the permutation N.
• on the second line: N different positive integers, each with a value between 1 and N – the permutation that the jury has come up with.

If you make an illegal call or you find the permutation incorrectly the output will contain appropriate message. Otherwise, the output of that program will be the massage “Correct!” and the value of the variable P, calculated as described earlier.