18159번 - Have You Ever Sorted an Array? 서브태스크언어 제한함수 구현

이제부터 여러분은 교준이와 간단한 게임을 하게 된다.

교준이는 마음속으로, 1부터 N까지 N개의 자연수로 이루어진 수열 A를 생각한다. 교준이는 여러분에게 자연수 N만 알려준다. 아직 여러분은 수열 A를 정확히 알지 못한다.

여러분은 교준이 마음속에 있는 수열 A를 알아내기 위하여, 교준이에게 다음과 같은 질문을 할 수 있다.

• "수열 A의 a번째 수와 b번째 수 중 뭐가 더 커?" (1 ≤ a < b ≤ N)

최소한의 질문으로 수열 A를 정확하게 알아내는 것이 이 게임의 목표이다. 교준이와 본 게임을 진행하는 프로그램을 작성하시오.

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

Grader에서 기본으로 제공하는 함수는 다음과 같다.

• bool compare(int a, int b)
  • 수열 A에서 a번째 수와 b번째 수 중 어떤 수가 더 큰지 알려주는 함수이다. 여러분은 본 함수의 호출 횟수를 최소화해야 한다.
  • 수열 A의 b번째 수가 a번째 수보다 더 클 경우, 함수는 true를 리턴한다. 아닌 경우에는 false를 리턴한다.
  • 1 ≤ a < b ≤ N를 만족해야 한다. 이를 만족하지 않은 경우, Grader는 "Wrong Answer [1]"라고 판정한다.
  • 한 판의 게임 내에 너무 많은 질문을 한 경우, Grader는 "Wrong Answer [2]"라고 판정한다. Sample Grader는 "Wrong Answer [2]"를 판정하지 않는다.
• void answer(int a, int b)
  • 몇 번의 질문을 통해 수열 A를 정확하게 알아냈다면, 여러분이 생각하는 수열 A의 정보를 이 함수를 통해 교준이에게 알려줘야 한다.
  • 수열 A의 a번째 수가 b일 경우, answer(a, b)를 호출해야 한다.
  • 1 ≤ a ≤ N, 1 ≤ b ≤ N을 만족해야 하고, 만족하지 않은 경우 Grader는 "Wrong Answer [3]"라고 판정한다.
  • 한 판의 게임 내에, 같은 a에 대해 두 번 이상 함수를 호출한 경우, Grader는 "Wrong Answer [4]"라고 판정한다.
  • 한 판의 게임 내에, 본 함수를 N번 호출하지 않은 경우, Grader는 "Wrong Answer [5]"라고 판정한다.
  • 수열 A를 정확하게 알아내지 못한 경우, Grader는 "Wrong Answer [6]"라고 판정한다.

여러분은 다음과 같은 함수를 작성해야 한다.

• void init(int T, int N)
  • 프로그램을 실행하고 난 직후, 한 번만 호출한다. T는 여러분이 교준이와 하게 될 게임의 총 판수를 나타내는 자연수이다. N은 교준이가 생각한 수열의 길이를 나타내는 자연수이다.
• void sorting()
  • 이 함수의 호출은 게임 한 판의 시작을, 종료는 게임 한 판의 종결을 의미한다. 
  • 이 함수가 호출되면, 여러분은 교준이에게 질문을 함으로써, 수열 A를 정확하게 알아내야 한다.
  • 이 함수는 총 T번 호출된다.

Grader가 실행 도중, "틀렸습니다"라고 판정한 경우, 그 즉시 프로그램은 종료된다.

여러분은 제출할 소스 파일 안에서 다른 변수나 함수 등을 자유롭게 선언할 수 있다. 다만 입출력 함수를 호출하거나 파일에 접근하는 행위는 금지된다. 또한 Grader의 취약점이나 포인터를 이용하여, Grader의 숨겨진 변수에 접근하거나, 점수를 조작하는 등의 불법적 행위를 할 경우, 실격 처리될 수 있음에 유의하라.

여러분이 작성한 소스 코드를 테스트하기 위하여, Sample Grader가 제공된다. 제공되는 Sample Grader는 실제 채점에 활용되는 Grader와 다를 수 있다.

Sample Grader는 다음과 같은 정보를 Standard Input을 통해 읽는다. 여러분은 어떠한 입력도 받으면 안된다.

첫 번째 줄에 교준이와 할 게임의 총 판 수와 교준이가 생각한 수열 A의 길이를 의미하는 자연수 T, N이 공백을 사이에 두고 주어진다.

두 번째 줄부터 T개의 줄에 걸쳐, 수열 A를 나타내는 N개의 자연수가 공백을 사이에 두고 주어진다.

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

여러분이 T판의 게임에서 전부 수열 A를 정확하게 알아낸 경우 Sample Grader는 "Accept. Max Questions = %d"의 형태로 출력한다. 이때, "%d"는 여러분이 게임 한 판에서 함수 compare의 최다 호출 횟수를 나타내는 정수이다.

Sample Grader가 "틀렸습니다"라고 판정한 경우 Sample Grader는 "Wrong Answer [4]"와 같은 형태로 출력한다.

• 1 ≤ T ≤ 5 × 10⁴
• 1 ≤ N ≤ 7
• 1 ≤ A_i ≤ N (1 ≤ i ≤ N)
• A_i ≠ A_j (1 ≤ i < j ≤ N)

• grader.cpp: grader.cpp
• SORT.cpp: SORT.cpp
• SORT.h: SORT.h

• N ≤ 4

• N = 5

• N = 6

• 추가적인 제한은 없다.

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

위의 Interaction 과정은 실제 정해와 전혀 관련이 없으며, 단지 이해를 돕기 위해 만든 예시이다. 위 예시는 교준이와 게임 두 판을 하면서, 두 번 모두 우연히 교준이의 수열을 정확하게 맞추었다.