35267번 - 0.4% 확률로 애드혹 구성적 문제 서브태스크점수인터랙티브

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

피돌이와 피붕이는 순열을 맞추는 게임을 하고 있다. 피붕이는 길이 $N$인 순열 $P = (P_1, P_2, \cdots, P_N)$를 하나 숨겨 두었고, 피돌이는 최대 $3000$번의 질문을 통해 이 순열을 맞혀야 한다.

한 번의 질문에서 피돌이는 길이 $N$인 순열 $Q = (Q_1, Q_2, \cdots, Q_N)$를 제시할 수 있으며, 피붕이는 $\sum_{i=1}^{N} |P_i - Q_i|$의 값을 알려준다.

머리가 좋지 않았던 피돌이는 여러분에게 도움을 요청하였다. 피돌이가 숨겨진 순열 $P$를 정확히 알아낼 수 있도록 도와주자.

첫째 줄에 피붕이가 숨긴 순열 $P$의 길이를 뜻하는 양의 정수 $N$이 주어진다. $(1\le N\le 1000)$

이후 당신은 다음과 같은 인터랙션을 최대 $3000$번 하여 순열 $P$를 맞추어야 한다.

• $?\ Q_1\ Q_2\ \cdots \ Q_{N}$ : $\sum_{i=1}^{N} |P_i - Q_i|$를 반환한다. 이때, $Q$는 순열이여야 한다.

순열 $P$를 찾았다면, 다음과 같은 인터랙션을 통해 정답을 제출해야 한다.

• $!\ P_1\ P_2\ \cdots \ P_{N}$

각 출력 후에는 표준 출력 버퍼를 비워야 한다. 정답을 제출한 후에는 추가적인 출력 없이 프로그램을 종료해야 한다. 위의 조건을 만족하지 않는 비정상적인 출력을 하거나, 인터랙션 횟수가 $3000$번을 초과하거나, 잘못된 정답을 제출할 경우 혹은 등 의도되지 않은 결과가 나올 수 있음에 유의하라. 인터랙터는 비적응적이다.

모든 테스트 케이스에서 $N \leq 6$이다.

모든 테스트 케이스에서 $N \leq 9$이다.

추가적인 제약 조건이 없다.

각 테스트 케이스에서 사용한 인터랙션 횟수를 $Q$라 하자. 모든 테스트 케이스에서 $Q$의 최댓값을 $M$이라 할 때, 점수는 다음과 같이 계산된다.

길이가 $N$인 순열이란 순열의 원소로 $1$부터 $N$까지의 정수가 모두 빠짐없이 단 한 번씩 나오는 수열을 의미한다. 즉, 순열 $A = \left(A_1, \, A_2 , \, \cdots, \, A_N\right)$는 아래 조건을 만족한다.

• $A_i$는 $1$ 이상 $N$ 이하의 정수
• $i \neq j$이면 $A_i \neq A_j$

언어 별로 표준 출력 버퍼를 비우는 방법은 다음과 같다. 기타 언어의 경우 각 언어의 documentation을 참조하라.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java: System.out.flush()
• Python: sys.stdout.flush()