## SGS Programming Challenge P2 - Vending Machine in Lunch

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

It's lunchtime, and as usual, Andy is trying to buy drinks from the vending machine.

The vending machine wants to play a game with Andy.

The vending machine hides a -indexed array consisting of distinct integers from to . The vending machine defines the rank of a number as the number of numbers smaller than it in the array.

Andy will try to find the index of the numbers in array with rank , where is the largest number such that . In other words, find the indices of the numbers .

Andy struggles to get the answer and asks you to help out.

You can perform two types of queries:

Query 1: You provide the vending machine with two indices and , and the vending machine will compare the two numbers at those indices and output 1 if and 0 if . This query costs dollar.

Query 2: You provide the vending machine with an array of size which consists of distinct integers for all indices in and an integer . The machine will return an integer , which is the index of the ranked number within the array . is given as the index in the original -indexed array . This query costs dollars.

You need to get the answer by spending at most dollars.

#### Constraints

All integers in are distinct.

#### Interaction

This is an interactive problem. The first line of input contains an integer .

To ask query 1, you output the following:

(followed by \n character)

To ask query 2, you output the following:

(followed by \n character)

If you believe you found the answer, output followed by , where is the largest integer such that , followed by integers (followed by \n character), representing the numbers with rank , respectively. You must terminate your program immediately after performing this operation. Note that this operation does not cost anything.

If at any point your query is malformed or your cost exceeds dollars, your program will receive -1, and the interactor will terminate. Upon receiving -1, your program should terminate to avoid an undefined verdict.

If you attempt an invalid operation (such as an invalid output format), you will receive a Presentation Error verdict.

If you exceed a cost of dollars, query incorrectly, or output incorrect final result, you will receive a Wrong Answer verdict.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

#### Sample Interaction

>>> denotes your output. Do not print this out.

The array is .

7
>>> ? 1 3
1
>>> ? 5 6
0
>>> $7 0 1 2 3 4 5 6 0 5 >>>$ 4 0 2 4 6 3
2
>>> ! 2 6 4 3

#### Explanation for Sample

For the first query, , so it prints .

For the second query, , so it prints .

For the third query, the whole array is being asked, and at index is ranked . Thus, it prints .

For the fourth query, the array is being asked. The number with a rank of is , with an index of in array . Thus, it prints .

For the final operation, . The number has index . The number has index . The number has index .

The total cost of this interaction is dollars, which is less than dollars.