보고 정렬

시간 제한4초메모리 제한1024 MB

요약

선택한 연속 구간을 무작위로 섞는 연산만으로 숨겨진 순열을 정렬하는 문제다.

문제

Bogo sort는 정렬이 될 때까지 랜덤 셔플을 반복하는 정렬 알고리즘이다.

이 문제에서 Grader는 0부터 (N - 1)까지의 정수로 이루어진 길이 N의 순열 A0, ..., A**N-1을 가지고 있다. 여러분은 순열에서 어떤 연속한 구간을 잡아 랜덤 셔플하는 동작만을 반복하여 그 순열을 정렬해야 한다.

다행히, 랜덤 셔플이 어떻게 이루어졌는지 '보고' 다음 동작을 결정할 수 있다.

Sample Grader는 다음과 같은 정보를 표준 입력을 통하여 읽어들인다. 여러분은 어떠한 입력도 받으면 안 된다.

첫 번째 줄에 순열의 길이를 나타내는 자연수 N이 주어진다.

두 번째 줄에 N개의 정수 A0, ..., A**N-1이 사이에 공백을 두고 주어진다.

Sample Grader는 다음과 같은 정보를 표준 출력을 통하여 출력한다. 여러분은 어떠한 출력도 하면 안 된다.

여러분이 올바르게 순열을 정렬한 경우, Sample Grader는 첫 번째 줄에 "Accepted"를 출력한다. 또한 두 번째 줄에 두 함수 copy_array와 shuffle_array를 호출한 횟수를 각각 출력한다.

모든 입력 데이터는 다음 조건을 만족한다.