DMPG '19 S5 - Secret Sort

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 4.5s
Memory limit: 256M

Author:
Problem type

Roger has a secret array a_1, a_2, \dots, a_N. Every number from 1 to N appears exactly once in this array. Roger needs help with sorting his array, but he doesn't want to show it to you. Instead, he will let you choose indices i, j to swap and after each swap, he will only tell you the number of inversions of the array. Help Roger sort his array!

Clarification: The number of inversions of an array a is the number of pairs of indices (i, j) for which i<j and a_i>a_j.

Constraints

For all subtasks:

At most 4\,000 swaps are allowed.

Subtask 1 [10%]

1 \le N \le 80

Subtask 2 [10%]

1 \le N \le 200

Subtask 3 [30%]

1 \le N \le 1\,000

Subtask 4 [50%]

1 \le N \le 2\,000

Input Specification

The first and only line of input is a single integer, N.

Interaction

This is an interactive problem. After reading the initial line of input, your program can make updates.
Each update must be a single line containing two space-separated integers, indicating which indices to swap. These integers must be between 1 and N and do not have to be distinct.
After printing, a new line with a single integer will appear as input. This integer is the number of inversions in the secret array after swapping.
Once you believe the array is sorted, print a single line containing 0. If the array is not sorted at this point, you will receive a WA verdict. Otherwise, you will receive AC.
You may make at most 4\,000 swaps (note that the final 0 is not considered a swap).

Sample Interaction

>>> denotes your output. You should not print this in your actual program.

4
>>>1 1
4
>>>4 3
5
>>>1 2
6
>>>1 4
1
>>>2 3
0
>>>0

Explanation for Sample

The original array is 3 4 1 2.

The array, after the swaps, is

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

Comments

There are no comments at the moment.