Small Numbers Search

시간 제한2초메모리 제한1024 MB

요약

크기 n인 숨겨진 순열에서 값 1부터 k까지의 위치를 찾는다. 두 위치의 값을 비교하는 질의를 10700번까지 사용한다.

난이도: 보통10점 중 7점
유형: 분할 정복, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

This is an interactive problem.

Jury has a permutation of numbers from $1$ to $n$ . Your task is find positions where numbers from $1$ to $k$ are placed. To do this, you can use jury's program which can compare numbers in any two positions in the permutation.

입력

The first line of input contains two integers $n$ and $k$ : the order of permutation and the number of positions to find. In all tests except the example, $n = 10\\,000$ and $k \le 10$ .

Then follow the answers for your requests, one per line. If the first of the two numbers to compare is less than the second one, the line will contain a single character "<", otherwise, it will contain a single character ">".

출력

If you want to compare numbers on positions $i$ and $j$ , you must print one line "? $i$ $j$ ". Here, $i$ and $j$ must be different integers between $1$ and $n$ . You can request a comparison at most $10\\,700$ times.

If you found all positions for all numbers from $1$ to $k$ , print "! $pos\_1$ $pos\_2$ $\dots$ $pos\_k$ ", and then terminate your program.

To prevent output buffering, after printing each line, consider issuing the command which flushes the buffer. For example, this command may be fflush(stdout) in C or C++, System.out.flush() in Java, flush(output) in Pascal or sys.stdout.flush() in Python.

Also, don't forget to put a newline at the end of every line of your output.

힌트

In the example, the jury's permutation is 1 2 3.

예제1

예제 1

입력

3 3
(waiting for output)
<
(waiting for output)
>
(waiting for output)
<

예상 출력

(reading input)
? 1 2
(reading input)
? 3 1
(reading input)
? 2 3
(reading input)
! 1 2 3
(terminating)