Wesley's Anger Contest Reject 5 - Two Permutations

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 5.0s
Memory limit: 256M

Problem types

Pesley has randomly generated two hidden permutations A and B of length N (or at least as random as a computer can). The permutation contains distinct values from 1 to N. He wants you to find any indices i and j such that A_i = B_j. Of course, he won't make it that easy and will only give you 10\,000 guesses to do so. After making a guess, he will respond with the values of A_i and B_j. 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:

1 \le N \le 300\,000
A and B are selected uniformly at random (subject to the limitations of a computer).

Subtask 1 [15%]

1 \le N \le 10

Subtask 2 [17%]

1 \le N \le 10\,000

Subtask 3 [68%]

No additional constraints.


The first line contains the integer N, the length of the permutations.

You will then begin making guesses. For each guess, output two space-separated integers i, j on a single line terminated by a \n character. 1 \le i \le N and 1 \le j \le N must be satisfied. Pesley will then respond with two space-separated integers A_i, B_j (followed by a \n character), representing the values in the first and second permutations at indices i and j. If A_i = B_j, 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 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.

>>> 1 2
3 4
>>> 4 3
4 2
>>> 3 1
1 1

Sample Explanation

In this example, A = [3, 2, 1, 4] and B = [1, 4, 2, 3]. (1, 3) is one possible pair of indices as A_3 = B_1 = 1.


There are no comments at the moment.