CPC '19 Contest 1 P4 - Sorting Practice

View as PDF

Submit solution


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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Today we will be practicing sorting! You and your friend are tasked to sort an array A of length N, (with elements A_1, A_2, \dots, A_N). To make your task more challenging, you will be blindfolded and will not be able to see this array.

You will be allowed to give directions to your friend a maximum of 50\,000 times. You can either ask your friend to compare elements A_i and A_j or swap elements A_i and A_j, as long as 1 \le i < j \le N and j - i + 1 = 2^k for some integer k \ge 1. Your friend will provide feedback after each direction. Can you determine a sequence of directions to sort the array?

Note: it is not required to sort the array with the minimum number of directions.

Constraints

For all subtasks:

1 \le A_i \le N (you will not be directly given A_i though)

At most 50\,000 directions are allowed.

Subtask 1 [10%]

1 \le N \le 100

Subtask 2 [90%]

1 \le N \le 1000

Interaction

The first line of input contains a single integer N, the size of the array.

You are then allowed to give directions to your friend.

To tell your friend to compare elements A_i and A_j, output C i j followed by a new line character \n. If the direction is valid, your friend will respond with 1 if A_i < A_j, or 0 if A_i \ge A_j.

To tell your friend to swap elements A_i and A_j, output S i j followed by a new line character \n. If the direction is valid, your friend will respond with 1.

After giving between 0 and 50\,000 directions, you can tell your friend that the array is sorted by outputing A followed by a new line character \n and terminating immediately. This does not count as a direction. Your friend will not respond after this direction. If the array is indeed sorted, then you will receive a verdict of Accepted. Otherwise, you will receive a verdict of Wrong Answer.

If at any point, you give an invalid direction (eg. the conditions 1 \le i < j \le N and j - i + 1 = 2^k for some integer k \ge 1 are not satisfied, or if you exceed 50\,000 directions), your friend will respond with -1. 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. Otherwise, the verdict may be undefined.

Please note that you may need to flush stdout before reading your friend's response. 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.

N = 4, A = [4, 2, 3, 3]

4
>>> C 2 3
1
>>> S 1 4
1
>>> C 1 2
0
>>> S 1 2
1
>>> C 2 3
0
>>> A

Comments


  • 1
    Plasmatic  commented on Oct. 28, 2019, 12:10 a.m.

    interactor should be fixed now