28141번 - Easy Interactive Problem 인터랙티브

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

$1$부터 $N$까지의 정수로 이루어진 길이 $N$의 순열 $A_1, A_2, \dots, A_N$이 있다. 처음에 여러분은 $A$의 각 원소가 어떤 값인지 알지 못하는 상태이다.

여러분은 채점기에 다음 질문을 최대 $\lfloor{3N/2}\rfloor$번 해서 순열 $A$의 각 원소가 어떤 값을 가지는지 알아내야 한다.

• ? x k: $x := A_x$를 $k$번 수행한다. 모든 연산을 완료했을 때 $x$의 값은 무엇인가?

물론 이대로라면 문제가 너무 쉬워진다. 그래서 이 문제에서는 특별히 질문을 할 때 사용하는 $k$의 값이 모두 달라야 한다는 제약이 있다.

순열 $A$는 첫 질문을 하기 전에 이미 정해져 있는 상태이다. 제한된 정보만으로 순열 $A$는 어떤 값들을 가지고 있을지 맞혀보자.

첫째 줄에 수열의 길이 $N$이 주어진다. ($1 \le N \le 1000$)

여러분은 다음 두 가지 유형의 질문을 채점기에 할 수 있다.

• ? x k: $x := A_x$를 $k$번 수행한 뒤의 $x$의 값을 질문한다. 질문은 아래 제약 사항을 모두 만족해야 하며, 반환값은 항상 $1$ 이상 $N$ 이하의 정수이다.
  • $x$는 $1 \le x \le N$ 를 만족하는 정수이다.
  • $k$는 $1 \le k \le 10^9$ 을 만족하는 정수이다.
  • 이 유형의 질문은 최대 $\lfloor {3N / 2} \rfloor$번 할 수 있다.
  • 질문을 할 때 사용하는 $k$의 값은 모두 달라야 한다.
• !$A_1\ A_2\ \dots\ A_N$: 여러분이 추측한 순열 $A$가 채점기에 정해진 순열과 일치하는지 질문한다. 별도의 반환값은 없고, 일치한다면 맞았습니다 판정을 받고 불일치한다면 틀렸습니다 판정을 받는다. 판정을 받은 뒤에는 프로그램이 즉시 종료된다.

질문을 한 뒤에는 반드시 개행 문자를 출력한 뒤 표준 출력 버퍼를 비워야 한다.

다음과 같은 경우에는 예상하지 못한 채점 결과를 받을 수 있음에 유의한다.

• 매번 질문을 한 뒤나 마지막에 $A$의 원소를 출력한 뒤 표준 출력 버퍼를 비우지 않았다.
• 출력 형식을 어겼다.
• $\lfloor {3N / 2} \rfloor$번보다 더 많은 질문을 했다.
• 잘못된 답을 출력했다.

예제는 입출력이 어떤 방식으로 이루어지는지 알기 쉽도록 의도적으로 줄 간격을 조정한 것으로, 실제 입출력과는 다르다.

언어별로 표준 출력 버퍼를 비우는 방법은 다음과 같다.

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