Тогуз коргоол


Отправить решение Решать в редакторе

Сложность: 80%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Тогуз коргоол («девять шариков») — кыргызская интеллектуальная игра, одна из дисциплин 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-битные целые числа.


Комментарии

Еще нет ни одного комментария.