시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB32266.667%

문제

Sashka regularly takes part in online programming competitions. The prize for the current one is participation in a summer programming camp in the Maldives. Especially 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, \dots , 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 ≤ x, y ≤ N$), is it true that $p_x < p_y$?
  2. Given a number $d$ and two positions $x$ and $y$ in the permutation ($1 ≤ x, y, d ≤ N$), is it true that $|p_x − p_y| ≡ 0 \pmod 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.

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.

구현

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 has 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 has the following prototype:

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

The function will return true, if $|p_x − p_y| ≡ 0 \pmod d$ and false otherwise.

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

You must submit the file sorting.cpp to the system which contains 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"

제한

  • $2 ≤ N ≤ 500\,000$
  • $1 ≤ p_i ≤ N$ for each $1 ≤ i ≤ N$.
  • $p_i \ne p_j$ for each $1 ≤ i < j ≤ N$.

점수

  • In tests worth $20$% of the points: $N ≤ 500$
  • In tests worth $30$% of the points: $N ≤ 2000$
  • In tests worth $40$% of the points: $N ≤ 10\,000$
  • In tests worth $60$% of the points: $N ≤ 75\,000$
  • In tests worth $100$% of the points: $N ≤ 500\,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 ≤ Q ≤ \frac{N}{2}$, $P = 1.00$.
  • If $\frac{N}{2} < Q ≤ N$, $P = 0.70$.
  • If $N < Q ≤ 2N$, $P = 0.50$.
  • If $2N < Q ≤ N\lceil \log_2{N} \rceil$, $P = 0.15$.
  • If $N\lceil \log_2{N} \rceil < Q ≤ N(1 + \lceil \log_2{N} \rceil)$, $P = 0.10$.
  • If $N(1 + \lceil \log_2{N} \rceil) < Q$, $P = 0.05$.

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

예제

Contestant function The jury’s program
Calls solve ( 3 )
Calls compare ( 1, 2 ) Returns value true
Calls compare ( 1, 3 ) Returns value false
Calls divisible ( 1, 3, 2 ) Returns value false
Returns { 2, 3, 1 }

테스트

For local testing you are provided with the files sorting.h and Lgrader.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 an appropriate message. Otherwise, the output of that program will be the massage “Correct!” and the value of the variable $P$, calculated as described earlier.

제출할 수 있는 언어

C++17, C++20, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 100점 이상을 획득해야 를 받는다.
  • 예제는 채점하지 않는다.