18192번 - 보고 정렬 언어 제한함수 구현

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

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

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

여러분의 프로그램은 제공되는 "bogoSort.h" 파일을 include 해야 한다.

여러분은 아래와 같은 함수를 구현해야 한다.

• void sort_array(int N)
  • N은 그레이더가 가진 순열의 길이 N을 의미한다.
  • 이 함수는 프로그램이 실행될 때 정확히 한 번 호출된다.
  • 이 함수가 종료될 때, 순열은 정렬되어 있어야 한다. 즉, 모든 0 ≤ i < N에 대해 A_i = i가 성립해야 한다.

여러분은 아래와 같은 함수를 호출할 수 있다.

• vector <int> copy_array()
  • 이 함수는 Grader가 가진 순열 A₀, ···, A_N-1를 반환한다.
  • 여러분은 이 함수를 최대 2,500회 호출할 수 있다.
• void shuffle_array(int s, int e)
  • 0 ≤ s ≤ e < N 이 성립해야 한다.
  • 이 함수가 호출되면 Grader는 순열의 구간 [s, e]를 랜덤 셔플한다.
  • 여러분은 이 함수를 최대 2,500회 호출할 수 있다.

함수의 자세한 동작 과정은 Sample Grader를 참고하라.

제공되는 Sample Grader는 실제 채점에 활용되는 Grader와 다를 수 있음에 유의하라. 단, 채점에 사용되는 Grader의 copy_array, shuffle_array 함수는 Sample Grader와 동일하게 구현되어 있다.

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

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

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

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

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

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

• 1 ≤ N ≤ 200
• 0 ≤ A_i < N (0 ≤ i < N)
• A_i ≠ A_j (0 ≤ i < j < N)

• Sample Grader: grader.cpp
• bogoSort.h: bogoSort.h
• bogoSort.cpp: bogoSort.cpp