Тогуз коргоол
Тогуз коргоол («девять шариков») — кыргызская интеллектуальная игра, одна из дисциплин VI Всемирных игр кочевников, прошедших в Кыргызстане в сентябре 2026 года. Студенты ОшГУ пишут программу-судью для турнира по обобщённому тогуз коргоолу, в котором лунок может быть сколько угодно, а коргоолов (камней) — очень много.
Доска. Есть два ряда по n лунок. Лунки пронумерованы от 1 до 2n по кругу: лунки 1, …, n — ряд Айбека (слева направо), лунки n + 1, …, 2n — ряд Бакыта, за лункой 2n снова идёт лунка 1. В лунке i сначала лежит a[i] камней. У каждого игрока есть казан — копилка выигранных камней, сначала пустая.
Ход. Игроки ходят по очереди, начинает Айбек. Ход задаётся номером j (от 1 до n) лунки в ряду ходящего: для Айбека это лунка j, для Бакыта — лунка n + j. Игрок берёт все камни из этой лунки и раскладывает их по одному в лунки по кругу (в сторону возрастания номеров), причём первый камень кладётся в ту же лунку, из которой камни взяты. Исключение: если в лунке был ровно один камень, он перекладывается в следующую лунку.
Взятие. Если последний камень попал в лунку соперника и в ней стало чётное число камней, ходящий забирает все камни этой лунки в свой казан.
Туздук. Если последний камень попал в лунку соперника и в ней стало ровно три камня, эта лунка становится туздуком ходящего (три камня идут в его казан), но только если одновременно:
- у ходящего ещё нет туздука (у каждого игрока может быть не больше одного туздука за игру);
- это не последняя (
n-я) лунка ряда соперника; - у соперника нет туздука с тем же номером в ряду (если туздук соперника —
k-я лунка ряда ходящего, нельзя сделать туздукомk-ю лунку ряда соперника).
Туздук остаётся навсегда. Каждый камень, который при раскладке попадает в туздук, сразу уходит в казан его владельца. Из туздука ходить нельзя.
Если игрок выбирает пустую лунку или туздук, ход пропускается (очередь всё равно переходит к сопернику).
Дана начальная расстановка и последовательность из m ходов. Выведите итог.
Входные данные
В первой строке — целое число n (1 ≤ n ≤ 200 000).
Во второй строке — 2n целых чисел a[1], …, a[2n] (0 ≤ a[i] ≤ 10⁹).
В третьей строке — число m (1 ≤ m ≤ 500 000), в четвёртой — m чисел j (1 ≤ j ≤ n): ходы по порядку (нечётные — Айбека, чётные — Бакыта).
Выходные данные
В первой строке выведите два числа — содержимое казанов Айбека и Бакыта.
Во второй строке — номера лунок-туздуков Айбека и Бакыта (0, если туздука нет).
В третьей строке — 2n чисел: сколько камней лежит в каждой лунке после всех ходов (в туздуках — 0).
Пример 1
Вход:
9
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
6
9 3 6 7 7 7
Выход:
26 10
17 0
11 11 1 10 10 2 1 12 3 12 12 3 13 1 12 1 0 11
Пояснение
Это начальная позиция настоящей игры: по 9 камней в 9 лунках. Первым ходом Айбек берёт 9 камней из лунки 9 и раскладывает их в лунки 9, 10, …, 17. В лунке 17 (восьмая лунка Бакыта) становится 10 камней — чётное число, и Айбек забирает их в казан. Позже Айбек делает туздуком ту же лунку 17.
Система оценивания
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 20 | n = 9, все a[i] = 9, m ≤ 1000 (как в настоящей игре) |
| 2 | 20 | n ≤ 100, a[i] ≤ 30, m ≤ 2000 |
| 3 | 60 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Примечание
Камней всего может быть до 4 · 10¹⁴ — используйте 64-битные целые числа.
Комментарии