Sorting
Time limit1sMemory limit1024 MB
Recover a hidden permutation of 1 to N using as few position comparisons as possible, with unlimited checks of whether a difference is divisible by any d.
- Level
Hard8 of 10
- Topics
- Number theory, Sorting, Math
- Solved
- No attempts yet
Problem
Sashka takes part in online programming competitions on a regular basis. The prize for the current one is a spot at a summer programming camp in the Maldives. For this contest, Sashka set her username to Sorting. One of the tasks is the following:
The jury has chosen a permutation p_1, p_2, p_3, ..., p_N of the numbers from 1 to N. To recover the permutation, you can ask the jury two types of questions:
- Given two positions x and y (1 ≤ x, y ≤ N), is p_x < p_y?
- Given a number d and two positions x and y (1 ≤ x, y, d ≤ N), is |p_x − p_y| ≡ 0 (mod d)? In other words, is the difference of the elements at positions x and y divisible by d?
You must ask as few questions of the first type as possible (see the scoring section below). Questions of the second type are unlimited.
Help Sashka by writing a program sorting that, given N, restores the permutation. It must contain the function solve, which will be compiled and executed together with the jury's program.
Constraints
2 ≤ N ≤ 500,000 1 ≤ p_i ≤ N for each 1 ≤ i ≤ N. p_i ≠ p_j for each 1 ≤ i < j ≤ N.