The combination lock to Josh's locker requires a sequence of specific integers to be input in a specific order. Josh bets that you won't be able to find this sequence!
Josh allows you to make up to different queries in order to determine the sequence. In each query, you can select two integers such that . Then, he will tell you the bitwise XOR of all integers from -th to the -th (-indexed) position in the sequence.
Let be the minimum value of amongst all queries. To make things harder, Josh challenges you to maximise the value of whilst still finding the sequence!
Can you successfully find Josh's sequence?
All integers in Josh's sequence are greater than and strictly less than .
If you find Josh's sequence correctly, with the maximum possible value of , you will score of the points.
If you find Josh's sequence correctly, but do not maximise the value of , you will score of the points.
Otherwise, you will score of the points.
This is an interactive problem, where the interactor is adaptive.
At first, you should read in a single integer on a single line, representing the value of .
Then, you will have the opportunity to make up to queries. To make a query, output a line in the form
? l r. Then, you should read in a single integer on a single line, representing the bitwise XOR of all elements from the -th to the -th positions in the sequence.
Finally, once you have made all of your queries, you should output a line in the form
! a_1, a_2, ..., a_N, where is the sequence which you believe is Josh's sequence.
If at any point you format your queries incorrectly, or ask more than queries, the interactor will respond with on a single line. After receiving this feedback, you should terminate your program to receive a Wrong Answer verdict; otherwise, your program will receive an arbitrary verdict.
If you successfully guess the correct sequence, then you will receive an Accepted verdict for that test case. Your final score for the problem will be equal to the minimum percentage of points received for any test case.
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.
3 >>> ? 1 2 5 >> ? 1 3 0 >> ? 2 3 1 >> ! 1 4 5
Josh's sequence is the sequence .
For the first query, the bitwise XOR of the elements between the -st and -nd positions is .
For the second query, the bitwise XOR of the elements between the -st and -rd positions is .
For the third query, the bitwise XOR of the elements between the -nd and -rd positions is .
Here, denotes the bitwise XOR operator.
The sequence has been correctly guessed, with . It can be shown that this is the maximum possible such that the sequence is guessable in queries, so this would score of the points.