| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 157 | 45 | 35 | 29.167% |
한버미는 길이가 $N$인 순열 $A$를 가지고 있다. 즉, $A$는 $1$ 이상 $N$ 이하의 정수들이 정확히 한 번씩 등장하는 수열이다. 당신은 한버미만 알고 있는 순열 $A$에서 $A_x=\left\lfloor\frac{N}{2}\right\rfloor+1$인 인덱스 $x$를 찾아야 한다. 이를 위해 당신은 한버미에게 아래와 같은 질문을 최대 $10^4$번 할 수 있다.
각 질문마다 당신은 길이가 $N$인 순열 $p$를 선택한다. 한버미는 $i$번째 막대의 높이가 $A_{p_i}$인 히스토그램 $H$를 생각한 뒤, $H$에 완전히 포함되면서 밑변이 히스토그램의 아랫변과 평행한 직사각형들 중 가장 넓이가 큰 직사각형을 하나 찾는다. 만약 가장 넓이가 큰 직사각형이 여러 개라면 그중 높이가 최대인 것을 아무거나 하나 찾는다. 선택한 직사각형의 밑변이 $l$번째 막대부터 $r$번째 막대까지의 밑변 전체와 같고 높이가 $h$일 때, 한버미는 세 정수 $l,r,h$를 답한다.
당신의 프로그램은 아래의 과정을 통해 표준입력과 표준출력으로 인터랙터와 상호작용해야 한다.
먼저, 입력의 첫 번째 줄에 정수 $N$이 주어진다.
아래 쿼리를 출력하면, 다음 줄에 쿼리의 답을 나타내는 세 개의 정수 $l, r, h$가 공백으로 구분되어 주어진다. 이 쿼리는 최대 $10^4$번만 사용할 수 있다.
? $p_1$ $p_2$ $\cdots$ $p_N$ (단, $p$는 길이 $N$의 순열)아래 쿼리를 출력해서 문제의 정답을 제출할 수 있다. 이 쿼리는 질문한 것으로 세지 않으며, 출력한 직후 프로그램을 종료해야 한다.
! $x$ (단, $1\le x\le N$)인터랙터는 비적응적이다. 즉, 인터랙션이 시작되기 전 순열 $A$는 정해져 있으며, 인터랙션이 진행되는 중에 변하지 않는다.
각 채점 데이터에 대하여, 제출한 답이 정답이라면 맞았습니다!!, 오답이라면 틀렸습니다 결과를 받는다. 단, 문제의 제한 안에 올바른 상호작용을 통해 답을 출력하지 못하면 예상치 못한 채점 결과를 받을 수 있다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 15 | $N\le 7$ |
| 2 | 85 | 추가 제약 조건 없음 |
3 1 2 2 1 1 3 1 2 2
? 1 2 3 ? 1 3 2 ? 2 1 3 ! 2
$A_1=3,A_2=2,A_3=1$의 예시다.
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 너비가 $1$로 일정하지만, 높이는 서로 다를 수도 있다. 예를 들어, 다음 그림은 높이가 $3, 5, 8, 8, 4, 7$인 직사각형으로 이루어진 히스토그램이다.

당신의 프로그램은 무언가를 출력한 후 즉시 출력 버퍼를 비워야 한다. 다음은 언어별 출력 버퍼를 비우는 방법이다.
fflush(stdout)std::cout.flush()sys.stdout.flush()System.out.flush()또한, 예제의 빈 줄은 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 추가된 것이며, 실제 입출력에는 빈 줄이 나타나지 않는다.
School > 한국과학영재학교 > 2026 KSA Automata Winter Contest F번