Каждое утро экспресс-поезд следует от фермы в город, а каждый вечер
он возвращается.
Беси знает, что у поезда есть \(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\)), и она хочет определить
минимальный ID-номер для каждого непрерывного множества из \(K\) вагонов.
У Беси есть ноутбук, на котором она может производить вычисления. Но он довольно
маленький, а её копыта - большие. Например, она не может написать все \(N+1-K\)
минимумов. Беси мычит ответы, после того, как вычислит их.
Поезд скоро прибудет, Помогите Беси определить \(N + 1 - K\) минимумов
когда поезд проезжает дважды, будьте уверены , что она использует свой ноутбук
эффективно. Её ноутбук поделен на \(5500\) секций, последовательно пронумерованных
\(0 \dots 5499\), и каждая секция имеет место, чтобы хранить ровно одно целое число
из интервала \(-2^{31}\) ... \(2^{31}-1\) включительно. Изначально в каждой секции
хранится число \(0\).
Это интерактивная задача, вы должны разработать следующую функцию,
которая поможет Беси использовать эффективно свой ноутбук.
void helpBessie(int ID);
Ваша функция будет вызываться с номером проходящего вагона в качестве
параметра.
Ваша реализация функции \(\texttt{helpBessie}\) должна вызывать следующие функции:
- int get(int index): получает значение целого числа,
которое хранится в ноубуке беси в данной ячейке index.
- void set(int index, int value): устанавливает значение целым числом value
в ячейке index
- 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}\) кроме обычного на 256 Мбт.
Однако между вагонами Беси не способна помнить ничего не содержащегося в её ноутбуке.
Поэтому между вызовами функции, Ваша программа не может хранить состояния -
а только использовать вызовы \(\texttt{get}\) и \(\texttt{set}\) calls.
Это означает:
Вам запрещено создавать глобальные или статические переменные.
Любое решение, которое делает это будет дисквалифицировано. Тренеры вручную
проанализируют решения, на это предмет. Вам также запрещено делать любые
операции ввода-вывода.
Общее количество вызовов \(\texttt{set}\) плюс общее количество вызовов
\(\texttt{get}\), сделанные Вашей программой должны быть ограничены \(25 \cdot 10^6\)
для каждого теста.