시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 (추가 시간 없음) 1024 MB 88 45 44 56.410%

문제

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

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

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

함수 목록 및 정의

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

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

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

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

  • vector <int> copy_array()
    • 이 함수는 Grader가 가진 순열 A0, ···, AN-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개의 정수 A0, ···, AN-1가 사이에 공백을 두고 주어진다.

출력

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

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

제한

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

  • 1 ≤ N ≤ 200
  • 0 ≤ Ai < N (0 ≤ i < N)
  • Ai ≠ Aj (0 ≤ i < jN)

제공 파일

예제 입력 1

4
2 0 1 3

예제 출력 1

Accepted
2 4

다음은 위의 입출력 예제에 대해서, Sample Grader와 Interaction하는 과정을 나타낸 것이다.

여러분이 작성한 코드 Grader 설명
  N = 4, A = {2, 0, 1, 3} Grader에서 NA0, ···, A3의 값을 읽어들인다.
  sort_array(4) 호출 sort_array 함수는 초기에 단 한 번만 호출된다.
copy_array() 호출    
  return {2, 0, 1, 3} 순열 A의 정보가 주어진다.
shuffle_array(0, 3) 호출    
  A = {1, 0, 3, 2} 순열 A를 랜덤 셔플한다.
copy_array() 호출    
  return {1, 0, 3, 2} 현재 순열 A의 정보가 주어진다.
shuffle_array(0, 1) 호출    
  A = {0, 1, 3, 2}  
shuffle_array(2, 3) 호출    
  A = {0, 1, 3, 2} 순열 A가 섞이지 않을 수도 있다.
shuffle_array(2, 3) 호출    
  A = {0, 1, 2, 3}  
sort_array(N = 4) 종료   여러분은 순열 A를 올바르게 정렬하였다.

위의 Interaction 과정은 실제 정해와 전혀 관련이 없으며, 단지 이해를 돕기 위해 만든 예시임에 유의하라.

제출할 수 있는 언어

C++14, C++17

채점

  • 예제는 채점하지 않는다.