You want to determine the heights of students (, which is a permutation from to ), but you do not have a measuring stick.
Instead, you can ask up to queries of types:
c i j: Query the index of the taller person (i.e., if , it will return ; if , it will return ).
h k: Query the height of the student.
You can ask up to
c queries and
Once you have the permutation, output
! followed by space-separated integers, representing the height of each student.
Can you recover their heights?
Subtask 1 [20%]
Subtask 2 [5%]
Subtask 3 [50%]
Subtask 4 [25%]
This is an interactive problem. The first line of input contains , , , and , representing the number of students, the number of
c queries you can make, the number of
h queries you can make, and the subtask of this test. Then, you will make at most queries and output the heights.
If you believe you have the correct list of heights, you may output
! followed by a space-separated list of integers (followed by a
\n character), representing your guess of the list of capacities in order from the first student to the last. You must terminate your program immediately after performing this operation. Note that this operation does not count towards the limit of operations.
The grader is not adaptive.
If at any point your query is malformed or you exceed the number of available queries, 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 invalid output format), you will receive a
Presentation Error verdict.
If you exceed the available query limit, query incorrectly, or output incorrect final heights, 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
cout << flush (depending on whether you use
cout). In Java, this can be done with
System.out.flush(). In Python, you can use
>>> denotes your output. Do not print this out.
The heights are .
5 300000 300 1 >>> c 4 3 3 >>> c 3 5 5 >>> c 5 2 2 >>> c 2 1 1 >>> ! 5 4 2 1 3
Since each comparison is strictly increasing, you know that the first query was a and progressively increases until . Additionally, this interaction outputs the correct heights and uses fewer
c queries than the maximum given (), so this solution will receive an