17690번 - Library 서브태스크다국어언어 제한함수 구현피드백

After several hundred years had passed, JOI city became a ruined city. IOI-chan, an explorer, is now exploring the area where the library was built. According to the results of exploration, the following are known:

• There were N books in the bookshelf of the library in JOI city. The N books were placed in the bookshelf in a line from left to right.
• The N books were numbered from 1 to N. But, the order of books in the bookshelf might be different from the order of the numbers of the books.
• By a single operation, it was possible to take contiguously placed books from the bookshelf at once.

Unfortunately, IOI-chan could not find old books in the library. But she found a machine which managed operations of the bookshelf of the library. If we specify one or more than one books by their numbers and send a query to the machine, it answers the minimum number of operations required to take only these books from the bookshelf.

IOI-chan wants to know the order of the books in the bookshelf by sending queries to the machine. However, because the answers from the machine would be the same if the order of the N books are reversed, she does not need to specify whether the books were placed from left to right or from right to left.

Because the machine is old, she can send at most 20 000 queries to the machine.

Write a program which specifies the order of the books in the bookshelf by sending at most 20 000 queries to the machine. It is not necessary to specify whether the books were placed from left to right or from right to left.

You need to submit one file.

The name of the file is library.cpp. It should implement the following function. The program should include library.h.

• void Solve(int N)
  For each test case, this function is called once.
  • The parameter N is the number of books N in the bookshelf.

Your program can call the following function.

• int Query(const std::vector<int>& M)
  ​​​​​​​If one or more than one books are specified by their numbers, this function returns the minimum number of operations required to take only these books from the bookshelf.
  • Books taken from the bookshelf are specified by the parameter M, which is a vector of size N. For each i (1 ≤ i ≤ N), if M[i-1] = 0, then the book i is not taken from the bookshelf. If M[i-1] = 1, then the book i is taken from the bookshelf. If the size of M is different from N, your program is considered as Wrong Answer [1]. For each i, M[i-1] should be equal to either 0 or 1. There should exist at least one i (1 ≤ i ≤ N) with M[i-1] = 1. If at least one of these two conditions is not satisfied, your program is considered as Wrong Answer [2]. If the function Query is called more than 20 000 times, your program is considered as Wrong Answer [3].
• void Answer(const std::vector<int>& res)
  ​​​​​​​Using this function, your program answers the order of the books in the bookshelf. It is not necessary to specify whether the books were placed from left to right or from right to left.
  • The parameter res is a vector of size N. It describes the order of the books in the bookshelf. For each i (1 ≤ i ≤ N), the i-th book from left in the bookshelf has number res[i-1]. If the size of res is different from N, your program is considered as Wrong Answer [4]. res[i-1] should be an integer between 1 and N, inclusive. If this condition is not satisfied, your program is considered as Wrong Answer [5]. Also, the integers res[0], res[1],. . ., res[N-1] should be different from each other. If this condition is not satisfied, your program is considered as Wrong Answer [6].

When the function Solve terminates, if the number of calls to the function Answer is different from 1, your program is considered as Wrong Answer [7].

If the order of the books specified by the function Solve is different from the order of the books in the bookshelf, your program is considered as Wrong Answer [8]. It is not necessary to specify whether the books were placed from left to right or from right to left.

• 1 ≤ N ≤ 1 000.
• 1 ≤ A_i ≤ N (1 ≤ i ≤ N).
• A_i ≠ A_j (1 ≤ i < j ≤ N).

Here is a sample input for sample grader and corresponding function calls.

5
4
2
5
3
1

In this task, it is not necessary to specify whether the books were placed from left to right or from right to left. Hence your program is considered as correct if it calls Answer( { 1,3,5,2,4 } ) whose parameters are reversed.

• dist.zip