Library
Time limit2sMemory limit512 MB
Given a hidden permutation of N books, query the oracle with a set of book numbers and receive the minimum number of contiguous-block removals needed to extract exactly those books, then recover the order.
- Level
Hard8 of 10
- Topics
- Intervals, Math, Combinatorics, Implementation
- Solved
- No attempts yet
Problem
Several hundred years have passed, and the city of JOI is now in ruins. IOI-chan, an explorer, is exploring the area where the library once stood. Her exploration has revealed the following.
- The library of JOI had N books on its bookshelf. The N books stood in a line on the bookshelf from left to right.
- The N books were numbered from 1 to N. The order of the books on the bookshelf might differ from the order of their numbers.
- In a single operation, it was possible to take contiguously placed books from the bookshelf at once.
Unfortunately, IOI-chan could not find the old books in the library. She did find a machine that managed the operations of the library's bookshelf. If we specify one or more books by their numbers and send a query to the machine, it answers with the minimum number of operations required to take only those books from the bookshelf.
IOI-chan wants to learn the order of the books on the bookshelf by sending queries to the machine. The machine gives the same answers when the order of the N books is reversed, so she does not need to determine whether the books were placed from left to right or from right to left.
The machine is old, so she can send at most 20 000 queries.
Write a program that determines the order of the books on the bookshelf using at most 20 000 queries. It is not necessary to determine whether the books were placed from left to right or from right to left.
Constraints
- 1 ≤ N ≤ 1 000.
- 1 ≤ Ai ≤ N (1 ≤ i ≤ N).
- Ai ≠ Aj (1 ≤ i < j ≤ N).