문제
수백 년의 시간이 지난 끝에, JOI 도시는 폐허가 되었다. 탐험가 IOI양은 도서관이 있었던 지역을 조사하고 있다. 조사를 통해 다음과 같은 것들을 알 수 있다.
• JOI 도시의 도서관 서재에는 N (1 <= N <= 1000)권의 책이 있었다. N 권의 책은 책장에 왼쪽에서 오른쪽으로 일렬로 놓여 있었다.
• N 권의 책은 1번부터 N번까지의 번호가 붙어있다. 하지만 책장에 꽂힌 순서와 번호가 붙은 순서는 다를 수도 있다.
• 작업 한 번으로 책장에서 연속으로 놓인 책을 가져갈 수 있었다.
유감스럽게, IOI양은 도서관에서 오래된 책을 찾는 데에 실패했다. 하지만 도서관의 작업을 담당하는 기계를 찾았다. 한 개 이상의 책 번호를 기계한테 물어볼 경우, 기계는 이 책들을 가져가기 위해서 필요한 작업의 최소횟수를 답해주었다.
IOI양은 기계에 질문을 하면서 책이 위치한 순서를 알고 싶어한다. 단, N개의 책이 역순으로 놓여있는 경우에도 답은 변하지 않으므로 왼쪽에서 오른쪽인지, 오른쪽에서 왼쪽인지의 방향은 신경 쓰지 않는다. 기계가 오래되었기 때문에 최대 20 000번의 질문만 할 수 있다.
입력
당신은 다음 함수를 구현해야 한다. 또한, library.h를 include해야한다.
• void Solve(int N)
이 함수는 각 테스트 케이스마다 정확히 한 번 불린다. 인자 N은 책의 수 N을 나타낸다.
당신의 프로그램은 다음 함수를 호출 할 수 있다.
– int Query(const std::vector<int>& M)
한 개 이상의 책 번호를 기계에 물어볼 경우, 이 함수는 책들을 가져가기 위해서 필요한 작업의 최소횟수를 반환한다.
∗ 가져갈 책의 번호들은 인자 M으로 표시되며, 이는 크기 N의 ‘vector‘이다. 각 i (1 ≤ i ≤ N) 에 대해, M[i-1]= 0인 경우, i 번째 책은 가져가지 않는다. M[i-1]= 1인 경우, i 번째 책은 가져간다. 만약 M의 크기가 N과 다를 경우 오답 [1]이 된다. 각 i에 대해, M[i-1]은 0 혹은 1이어야 한다. M[i-1]= 1인 i가 (1 ≤ i ≤ N) 적어도 한 개는 존재해야 한다. 이 두 조건을 만족하지 않을 경우 오답 [2]이 된다. Query를 20 000번 초과로 호출할 경우, 오답 [3]이 된다.
– void Answer(const std::vector<int& res)
이 함수를 이용하여 책꽂이에 꽂힌 책의 순서를 답할 수 있다. 책이 왼쪽에서 오른쪽인지, 오른쪽에서 왼쪽인지의 방향은 신경 쓰지 않는다.
∗ 인자 res는 크기 N의 ‘vector‘이다. 이는 책꽂이에 꽂혀있는 책의 순서를 나타낸다. 각 i (1 ≤ i ≤ N) 에 대해 책꽂이에 왼쪽에서 i 번째로 꽂혀있는 책의 번호는 res[i-1]이다. 만약 res의 크기가 N과 다를 경우, 오답 [4]이 된다. 만약 res[i-1]는 1 이상 N 이하의 수여야한다. 만약 이를 만족하지 않을 경우, 오답 [5]이 된다. 또한, 수 res[0], res[1], res[N-1]은 모두 달라야 한다. 만약 이를 만족하지 않을 경우, 오답 [6]이 된다.
Solve함수가 종료될 때, Answer함수를 호출한 횟수가 한 번이 아니면, 오답 [7]이 된다. 만약 Solve로 주어진 책의 순서가 책장에 꽂힌 순서와 다르면 오답 [8]이 된다. 왼쪽에서 오른쪽인지,
오른쪽에서 왼쪽인지의 방향은 신경쓰지 않는다.