기차 관측

매일 아침 급행열차가 농장을 지나 대도시로 향하고, 매일 오후에는 반대 방향으로 교외를 향해 지나간다. 오늘 베시는 아침과 오후 두 번 모두 시간을 내어 기차를 관찰하기로 했다.

베시는 기차에 \(N\)개의 차량이 있다는 것을 미리 알고 있다 (\(1 \leq N \leq 10^6\)). 차량들은 편의상 \(0 \dots N-1\)번으로 번호가 매겨져 있다. 차량 \(i\)에는 ID 번호 \(c_i\)가 적혀 있다 (\(0 \le c_i \le 10^9\)). 모든 번호는 아침과 오후에 모두 보이므로, 각 차량의 번호를 관찰할 기회는 두 번씩 있다. 즉, 아침에 기차가 지나갈 때 베시는 \(c_0\), 그 다음 \(c_1\), 이렇게 \(c_{N-1}\)까지 차례로 관찰할 수 있다. 오후에 기차가 지나갈 때에도 다시 \(c_0\), 그 다음 \(c_1\), 이렇게 \(c_{N-1}\)까지 차례로 관찰할 수 있다.

베시는 정수 \(K\) (\(1 \leq K \leq N\))를 하나 골랐고, 연속한 \(K\)개의 차량으로 이루어진 각 구간에 대해 최소 ID 번호를 구하고 싶어한다. 베시에게는 계산을 할 수 있는 공책이 있지만, 공책은 꽤 작은 데다 베시의 글씨(발굽글씨?)는 꽤 크다. 예를 들어, \(N+1-K\)개의 최솟값을 모두 적을 공간조차 없을 수 있다. 알 수 없는 이유로 베시는 최솟값을 계산하는 즉시 하늘에 대고 음매 하고 외치는 것으로 만족하므로, 적어도 이것은 문제가 되지 않는다.

기차가 곧 도착한다! 기차가 두 번 지나가는 동안 베시가 \(N + 1 - K\)개의 최솟값을 모두 찾을 수 있도록 도와주고, 제한된 공책 공간을 효율적으로 사용하도록 해 주자. 베시의 공책은 \(5500\)개의 칸으로 나뉘어 있으며, 편의상 \(0 \dots 5499\)번으로 번호가 매겨져 있다. 각 칸에는 \(-2^{31}\) 이상 \(2^{31}-1\) 이하의 정수를 정확히 하나 저장할 수 있다. 처음에 각 칸에는 정수 \(0\)이 저장되어 있다.

이 문제는 인터랙티브 문제이지만, 표준 입출력(또는 파일 입출력)을 사용하지 않는다. 특히, 베시가 제한된 공책 공간을 효율적으로 관리하도록 돕는 다음 함수를 구현해야 한다.

void helpBessie(int ID);

아침과 오후에 각 기차 차량이 지나갈 때마다 이 함수가 호출되며, 입력으로는 그 차량에 적힌 ID 번호가 주어진다.

\(\texttt{helpBessie}\) 함수의 구현에서는 다음 함수들을 호출할 수 있다.

• ** int get(int index)**: 베시의 공책에서 주어진 인덱스에 저장된 정수 값을 가져온다.
• ** void set(int index, int value)**: 주어진 인덱스의 정수를 주어진 값으로 설정한다.
• ** void shoutMinimum(int output)**: 베시가 주어진 수를 하늘에 대고 음매 하고 외치게 한다.
• ** int getTrainLength()**: 기차 차량 수 \(N\)을 반환한다.
• ** int getWindowLength()**: 윈도 길이 \(K\)를 반환한다.
• ** int getCurrentCarIndex()**: 현재 지나가고 있는 기차 차량의 인덱스를 반환한다.
• ** int getCurrentPassIndex()**: 베시가 아침 통과를 관찰 중이면 \(0\)을, 오후 통과를 관찰 중이면 \(1\)을 반환한다.

코드 작성을 돕기 위해 C/C++와 Java용 초기 템플릿이 제공된다. 아쉽게도 이 문제에서는 Python과 Pascal 제출이 지원되지 않는다.

윈도 최솟값은 순서대로 출력되어야 한다 (즉, 차량 \(0, 1, \dots, K-1\)에 대한 최솟값이 차량 \(1, 2, \dots, K\)에 대한 최솟값보다 먼저 출력되어야 한다). 하지만 이 순서 제약을 제외하면, 함수는 어떤 함수 호출 중에든, 어느 시점에든 최솟값을 출력할 수 있다. 예를 들어 어떤 호출에서는 아무 출력도 하지 않고, 다른 호출에서는 여러 개를 출력해도 된다.

베시는 초단기 기억력이 매우 뛰어나므로, \(\texttt{helpBessie}\) 함수 내부에서는 일반적인 256MB 제한을 제외하면 메모리 사용에 제한이 없다. 하지만 기차 차량과 차량 사이에는, 베시는 공책에 적혀 있지 않은 것은 아무것도 "기억"할 수 없다. 따라서 함수 호출 사이에는 \(\texttt{get}\)과 \(\texttt{set}\) 호출을 통하지 않고는 프로그램이 상태를 유지할 수 없다.

이는 다음을 의미한다.

** 상수가 아닌 전역 변수나 정적 변수를 만드는 것은 허용되지 않는다. 이를 어긴 풀이는 실격 처리된다. 코치들이 풀이가 문제의 취지를 따르는지 직접 검사할 것이다. 이 문제에서는 파일 입출력이 필요하지 않으므로, 코드에서 파일 입출력을 수행하는 것 역시 허용되지 않는다.**

프로그램이 수행하는 \(\texttt{set}\) 호출 횟수와 \(\texttt{get}\) 호출 횟수의 합은 각 테스트 케이스마다 \(25 \cdot 10^6\)회로 제한된다.

출제자: Dhruv Rohatgi

출제자: Dhruv Rohatgi

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > US Open > Platinum