Imprecise Permutation Sort#11140

Imprecise Permutation Sort

10 seconds

512 megabytes

Very hard

This is an interactive problem.

A permutation $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n of integers from $1$ to $n$ is hidden from you.

Your task is to sort it in ascending order by comparing and swapping pairs of elements. This problem could be pretty easy, but the jury member responsible for the problem was too concentrated on floating-point arithmetic in problems G and J and implemented an "imprecise" comparator:

if $\frac{∣ a _{i} - a _{j} ∣}{m a x ( a _{i} , a _{j} )} \leq 0.01$ \frac{|a_i - a_j|}{\max(a_i, a_j)} \leq 0.01, then return $0$ ;
otherwise, if $a_{i} < a_{j}$ a_i < a_j, then return $- 1$ ;
otherwise, return $1$ .

Your program can make queries to compare any two elements with this comparator, or to swap any two elements. After each swap, it will be told whether the permutation became sorted.

Sort a permutation of size up to $16384$ using no more than $300000$ queries.

Interaction

Receive an integer $n$ from the jury's program — the size of the permutation ( $1 \leq n \leq 16384$ 1 \leq n \leq 16\,384). Then print queries and receive responses from the jury's program. After each query the output should be flushed and then a single integer should be read — the response to that query.

Comparison queries have a format "C i j", and swap queries have a format "S i j", where $i$ and $j$ are indices of two elements ( $1 \leq i, j \leq n$ 1 \leq i, j \leq n). Making queries with $i = j$ i=j is allowed.

The response to a comparison query is $0$ if $a_{i}$ a_i "approximately equals" $a_{j}$ a_j, otherwise: $- 1$ if $a_{i} < a_{j}$ a_i < a_j, and $1$ if $a_{i} > a_{j}$ a_i > a_j.

A swap query swaps values in $a_{i}$ a_i and $a_{j}$ a_j, and the response to a swap query is $1$ if after this swap the array became sorted in ascending order, and $0$ otherwise.

Your program should exit as soon as it receives $1$ as a response to a swap query.

The program should make at least one swap query. For example, if the hidden permutation is already sorted, it can make a query "S 1 1", receive a $1$ , and exit.

The interactor is not adaptive. The initial permutation is chosen by the jury's program in advance, before you make your first query.

Examples

Example 1

Loading

Example 2

Loading

a_{1}, a_{2}, \dots, a_{n}

\frac{∣ a _{i} - a _{j} ∣}{m a x ( a _{i} , a _{j} )} \leq 0.01

a_{i} < a_{j}

1 \leq n \leq 16384

1 \leq i, j \leq n

i = j

a_{i}

a_{j}

a_{i} < a_{j}

a_{i} > a_{j}

a_{i}

a_{j}