Pesley has randomly generated two hidden permutations and of length (or at least as random as a computer can). The permutation contains distinct values from to . He wants you to find any indices and such that . Of course, he won't make it that easy and will only give you guesses to do so. After making a guess, he will respond with the values of and . Can you find any such pair of indices?
For this problem, you will NOT be required to pass ANY of the samples in order to receive points.
For all subtasks:
and are selected uniformly at random (subject to the limitations of a computer).
Subtask 1 [15%]
Subtask 2 [17%]
Subtask 3 [68%]
No additional constraints.
The first line contains the integer , the length of the permutations.
You will then begin making guesses. For each guess, output two space-separated integers , on a single line terminated by a
\n character. and must be satisfied. Pesley will then respond with two space-separated integers , (followed by a
\n character), representing the values in the first and second permutations at indices and . If , then you have found the indices and will receive an Accepted verdict. Otherwise, you can continue to make more guesses until you run out, in which case, you will receive a Wrong Answer verdict.
If at any point you attempt an invalid operation (such as an invalid output format, failure to provide any output, or index out of bounds),
-1 will be outputted (followed by a
\n character). When this happens, you should terminate your program to avoid reading from a closed input stream, and you will receive a verdict of
Wrong Answer (Presentation Error). Otherwise, the verdict may be undefined.
Please note that you may need to flush
stdout after each operation. 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.
4 >>> 1 2 3 4 >>> 4 3 4 2 >>> 3 1 1 1
In this example, and . is one possible pair of indices as .