이 문제는 인터랙티브 문제입니다.

디저트 축제의 개막을 앞두고, 수석 요리사는 가게의 대표작인 “千层幻彩慕斯”를 정성스럽게 다듬고 있습니다. 이 디저트는 서로 다른 맛의 무스 $n$개로 이루어져 있으며, 각각 $0,1,\dots,n-1$의 번호가 붙어 있습니다.

하지만 정신없는 와중에 조수가 실수로 무스의 배치 순서를 뒤섞었습니다. 이제 무스들은 왼쪽부터 오른쪽까지 일렬로 놓여 있으며, 알 수 없는 배치 순열 $p=(p_0,p_1,\dots,p_{n-1})$을 이룹니다. 여기서 $p_i$는 $i$번째 위치에 놓인 무스의 번호입니다.

각 무스의 정확한 위치를 알아내기 위해 디저트 검사기를 사용할 수 있습니다. 매번 서로 다른 세 위치 $x,y,z$를 고르면, 검사기는 그 세 무스의 가장 작은 번호와 가장 큰 번호의 합을 알려 줍니다.

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

곧 개막을 알리는 종이 울립니다. 제한된 횟수의 검사로 각 무스의 실제 위치를 정확히 복원할 수 있을까요?

길이가 $n$인 순열 $p$가 있으며, 그 원소는 정확히 $0,1,\ldots,n-1$입니다. 여러분은 $p$의 구체적인 내용을 모릅니다.

서로 다른 세 인덱스 $x,y,z$를 선택하면 인터랙션 라이브러리는 다음 값을 반환합니다.

$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$

여러분의 과제는 순열 전체를 복원하는 것입니다. 질의 횟수 제한과 질의 횟수에 따른 점수 계산 방법은 아래에 설명되어 있습니다.

구현 세부사항

참가자는 main 함수를 구현할 필요가 없으며, 구현해서도 안 됩니다. 제출하는 소스 파일에는 다음을 포함해야 합니다.

#include "mousse.h"

다음 두 함수를 구현해야 합니다.

void init(int c);
std::vector<int> mousse(int c, int n);

• $c$는 서브태스크 번호이며, $c=0$은 예제를 나타냅니다. 각 테스트 케이스는 정확히 하나의 데이터를 포함합니다. 인터랙션 라이브러리는 해당 테스트 케이스에 대해 init(c)를 한 번 호출한 후 mousse(c,n)을 한 번 호출합니다.
• mousse는 길이가 $n$인 배열을 반환해야 하며, 그 배열의 $i$번째 원소는 $p_i$여야 합니다. 인덱스는 $0$부터 시작합니다.

참가자는 다음 함수를 호출하여 질의 한 번을 수행할 수 있습니다.

int query(int x, int y, int z);

$0\le x,y,z < n$을 만족해야 하며, $x,y,z$는 쌍마다 서로 달라야 합니다. 이 함수는 $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$를 반환합니다.

프로그램 테스트 방법

첨부 파일에는 mousse.h, 로컬 인터랙션 라이브러리 grader.cpp, 예제 프로그램 template_mousse.cpp가 포함되어 있습니다. 자신의 프로그램을 mousse.cpp로 저장한 후, 이 문제의 디렉터리에서 다음 명령을 실행할 수 있습니다.

g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.in

로컬 인터랙션 라이브러리는 표준 입력에서 숨겨진 순열을 읽습니다. 참가자 프로그램은 이 데이터를 직접 읽어서는 안 됩니다. 입력 형식은 다음과 같습니다.

• 첫 번째 줄에는 두 정수 $c,n$이 주어집니다.
• 두 번째 줄에는 $p_0,p_1,\ldots,p_{n-1}$이 주어집니다.

답이 올바르면 인터랙션 라이브러리는 Correct!와 Max queries used: Q를 출력합니다. 여기서 $Q$는 해당 테스트 케이스의 질의 횟수입니다. 답이 틀리면 Wrong answer.를 출력합니다. 올바르지 않은 질의를 전달하거나 질의 횟수 제한을 초과하면 프로그램은 표준 오류에 오류 메시지를 출력한 뒤 종료합니다. -v 옵션을 추가하여 해당 테스트 케이스의 질의 횟수를 확인할 수 있습니다.

예제

입력 1

0 10
0 2 9 1 5 8 3 7 6 4

출력 1

Correct!
Max queries used: 15

참고

예를 들어 query(0,1,2)를 호출하면 대응하는 세 값은 $0,2,9$이며, $0+9=9$를 반환합니다. 참고 프로그램은 이 데이터에서 $15$번의 질의를 사용합니다. 다른 전략을 사용하면 이 횟수는 달라질 수 있습니다.

제한

모든 테스트 데이터에 대해 $n\in\{10,100,10^5\}$이며, $p$는 $0\sim n-1$의 순열입니다. 각 테스트 케이스는 정확히 하나의 데이터를 포함합니다.

예제에서는 $c=0$, $n=10$이며, 질의 횟수 제한은 $1000$입니다.

서브태스크

다음에 주의하세요.

• 인터랙션 라이브러리는 적응형이 아닙니다. 각 테스트 케이스의 순열은 참가자 프로그램을 호출하기 전에 이미 정해져 있으며, 질의에 따라 바뀌지 않습니다.
• 참가자는 표준 입력을 읽거나 다른 불법적인 방법으로 숨겨진 순열을 얻어서는 안 됩니다. 최종 채점에 사용하는 인터랙션 라이브러리의 구현은 로컬 인터랙션 라이브러리와 다를 수 있습니다.

어떤 테스트 케이스에서 mousse가 잘못된 답을 반환하거나, query의 인자가 올바르지 않거나, 질의 횟수가 해당 서브태스크의 $Q_{\max}$를 초과하면 그 테스트 케이스의 점수 배율은 $0$입니다.

서브태스크 $1,2$에서는 모든 테스트 케이스에 대해 정답을 구해야 해당 서브태스크의 모든 점수를 얻을 수 있습니다.

서브태스크 $3,4$에서는 어느 한 테스트 케이스라도 점수 배율이 $0$이면 해당 서브태스크는 $0$점을 받습니다. 그렇지 않으면 $Q$를 해당 서브태스크의 모든 테스트 케이스 중 최대 질의 횟수라고 할 때, 점수 배율 $f(Q)$는 다음 표에 따라 정해집니다.

$Q\le 99970$이면 $f(Q)=100\%$입니다. $Q$가 표의 서로 인접한 두 행 $(Q_i,f_i)$와 $(Q_{i+1},f_{i+1})$ 사이에 있으면 다음과 같습니다.

$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$

서브태스크 $3$의 점수는 $30f(Q)$이며, 서브태스크 $4$의 점수는 $60f(Q)$입니다. 최종 점수는 소수점 아래 $3$자리로 반올림합니다.

시간 제한: $10\ \mathrm{s}$.

메모리 제한: $512\ \mathrm{MiB}$.