Slopsort

Program time limit: 1 second

Program memory limit: 256 MB

There is an array containing each integer from $1$ to $n$ inclusive.

You would like to sort the array. However, the only operation you may perform is a slop:

• Select two integers $l$ and $r$ with $1 \le l < r \le n$.
• The array values from index $l$ to index $r$ (using 1-indexing) inclusive are shuffled randomly.

Sort the array using at most 500 slops.

Interaction

This is an interactive problem. Your program should do the following.

• Read a single integer $n$.
• Repeat the following:
  • Read $n$ integers, representing the current state of the array.
  • If the array is sorted, your program should terminate.
  • Otherwise, output two integers $l$ and $r$ for your next slop.
  • You must flush the output after each slop. In C or C++, you can use fflush(stdout). In Python, use print(l, r, flush=True).

If you attempt an invalid slop or perform 500 slops without sorting the array, then the next integer your program reads will be -1, and no further input will be provided to your program.

If using Python, you could use the following template.

N = int(input())
while True:
    A = list(map(int, input().split()))
    if A == [-1]:
        # we messed up
        exit()
    if A == [i+1 for i in range(N)]:
        # we succeeded
        exit()
    # Shuffle the first two values
    print(1, 2, flush=True)

Constraints

• For Subtask 1 (30% of points): $N = 5$.
• For Subtask 2 (30% of points): $N = 20$.
• For Subtask 3 (40% of points): $N = 100$.

Sample Interaction

5
4 2 3 1 5
                    1 4
1 3 2 4 5
                    2 3
1 3 2 4 5
                    2 3
1 2 3 4 5

Explanation 1

On the left is the input the program receives, and on the right is the output it produces.

The first slop randomly shuffles the first four values in the array.

The second slop shuffles the second and third values, but happens to do nothing.

The third slop shuffles the second and third values, and happens to swap them.

The array is now sorted, so the program terminates.

Scoring

For each subtask (worth 30%, 30% and 40% of points, as per the Constraints section), your program will be run on four (4) secret test cases one after another, and if it is successful for all test cases, it solves that subtask. Your program will receive the points for each subtask it solves. Recall that your final score on the task is the score of your highest scoring submission.

Submit unofficially

The contest ended at 8:45 p.m. AEST on Tuesday 7th April. All submissions will be unofficial officially.

Log in to submit!