Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2379. Медианный элемент
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на русском языке
| 03/11/2017 | Муниципальный этап 10-11 классы (3) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Будем называть `i`-й элемент последовательности `a_1,\ a_2,\ …,\ a_N` медианным, если количество элементов,
меньших или равных `a_i` среди элементов `a_1,\ a_2,\ …,\ a_{i-1}`, больше или равно количеству элементов, больших
или равных `a_i` среди элементов `a_{i+1},\ a_{i+2},\ …,\ a_N`. В последовательности может быть несколько медианных элементов.
Напишите программу, которая находит минимальный индекс медианного элемента.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 100000`). Вторая строка ввода содержит `N` целых чисел
в диапазоне от 1 до `10^9`, разделенных пробелами – последовательность `a_1,\ a_2,\ …,\ a_N`.
Вывести в первой строке одно целое число — минимальный индекс медианного элемента.
Пример ввода 1
4 1 2 5 10
Пример вывода 1
3
Пример ввода 2
4 10 5 2 1
Пример вывода 2
1
Описание подзадач и системы оценивания
Подзадача 1 (50 баллов)
`1\ ≤\ N\ ≤\ 1000`
В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1.
`1000\ <\ N\ ≤\ 100000`
В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
