28488번 - 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. 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 2ドルN < 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$.

힌트

예제

테스트

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.

첨부

• Lgrader.cpp sorting.h