시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 (추가 시간 없음) 1024 MB 171 82 69 46.309%

문제

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++17, C++14

채점 및 기타 정보

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