100 БАЛЛОВ СРОЧНО Задача 2. Реверс
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Стёпа и Гена сидят на очень скучном уроке и чтобы скоротать время, они играют в одну занимательную игру. Для игры требуется изначально пустое прямоугольное клеточное поле и много
камней белого и черного цвета. Стёпа всегда ходит белыми, а Гена черными камнями. Каждый
игрок в свой ход ставит камень своего цвета в любую свободную клетку. При этом, промежутки
между поставленным и ближайшим к нему камнем в каждом из четырёх направлений (влево, вправо, вверх, вниз) заполняются камнями этого же цвета. Если в каком-то направлении нет камня того
же цвета, то в этом направлении изменений не происходит. При этом, если в заполняемых промежутках встречаются камни противника, они убираются с поля. Игроки ходят по очереди, начинает
игру Стёпа.
Стёпа хочет знать после каждого хода, на сколько у него больше камней, чем у Гены, но он не
хочет тратить время на такое скучное занятие, как подсчёт камней. Поэтому он надеется на вашу
помощь.
Протокол взаимодействия
Это интерактивная задача, и в ней вам предстоит работать не с файловым вводом-выводом, а со
специальной программой — интерактором. Взаимодействие с ней осуществляется через стандартные
потоки ввода-вывода.
В начале вашей программе в стандартный поток ввода подаётся два целых числа N и M —
размеры поля по горизонтали и по вертикали соответственно (1 ⩽ N, M ⩽ 5000).
Далее на вход программы поступает информация об очередном ходе игроков, состоящая
из двух целых чисел: x и y, которые определяют координаты камня, поставленного на поле
(1 ⩽ x ⩽ N, 1 ⩽ y ⩽ M).
В ответ на это необходимо вывести одно целое число K — разницу количества камней Стёпы и
Гены на текущем ходу, при этом она может быть и отрицательной.
Добавление на поле камня с координатами (x = −1, y = −1) означает конец игры, в этом случае
решение должно завершиться. Гарантируется, что запросов не более чем 100.
Убедитесь, что после каждого ответа вы выводите символ перевода строки и очищаете буфер
потока вывода (команда flush языка). Иначе решение может получить вердикт Timeout.

Система оценки
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи
необходимых подзадач успешно пройдены

1 35 1 ⩽ N, M ⩽ 100
2 65 1 ⩽ N, M ⩽ 5000 1

Пример
стандартный ввод стандартный вывод
10 10
3 3
5 3
7 3
9 3
-1 -1
1
0
5

Для решения этой задачи потребуется правильно отслеживать размещение камней, их влияние на поле и корректно рассчитывать разницу между количеством камней Стёпы и Гены. Основные шаги решения можно разбить следующим образом:

1. Инициализация и чтение размеров поля

При старте программы нам сообщают размеры поля $N$ и $M$, что означает, что поле размером $N \times M$ будет содержать клетки, в которых изначально нет камней.

2. Механика ходов

• Стёпа и Гена ходят по очереди: Стёпа ходит белыми камнями, а Гена — чёрными.
• Когда игрок ставит камень в клетку $(x, y)$, происходит заполнение промежутков между этим камнем и ближайшими камнями того же цвета в четырёх направлениях (вверх, вниз, влево, вправо).
• Если в пути между новым камнем и другим камнем того же цвета встречаются камни противника, они убираются с поля.

3. Логика заполнения

После установки камня на поле нужно пройти по каждому из четырёх направлений:

• Для каждого направления (вверх, вниз, влево, вправо) искать ближайший камень того же цвета.
• Если на пути встречаются камни противника, они удаляются.
• Итог: только промежутки между новым камнем и ближайшими камнями того же цвета заполняются текущим цветом, а камни противника удаляются.

4. Подсчёт камней

После каждого хода необходимо:

1. Подсчитать текущее количество камней Стёпы и Гены на поле.
2. Вывести разницу между количеством камней Стёпы и Гены.

5. Обработка конца игры

Если на вход поступают координаты $(-1, -1)$, это сигнал завершения игры. В этом случае программа прекращает работу.

6. Оптимизация и производительность

Так как размеры поля могут достигать $5000 \times 5000$, хранить и обрабатывать все клетки напрямую может быть дорого по памяти. Поэтому важно:

• Использовать эффективные алгоритмы для поиска ближайших камней в четырёх направлениях (например, с использованием очередей или обходов).
• Оптимизировать подсчёт камней, так как делать это с нуля после каждого хода будет неэффективно. Можно хранить текущие суммы камней и изменять их только при необходимости.

Пример реализации на Python

Примерный код для такого подхода на Python может выглядеть следующим образом:

python
import sys
input = sys.stdin.read
output = sys.stdout.write
flush = sys.stdout.flush
# Чтение размеров поля
data = input().split()
N, M = int(data[0]), int(data[1])
# Инициализация поля
field = [[None] * M for _ in range(N)]
score_stepa = 0  # Количество камней Стёпы
score_gena = 0   # Количество камней Гены
turn = True      # True, если ход Стёпы, False, если ход Гены
# Вспомогательная функция для обновления поля и подсчета камней
def place_stone(x, y, color):
    global score_stepa, score_gena
    # Здесь нужно реализовать логику установки камня и заполнения промежутков
    # Обновляем количество камней в зависимости от поставленного камня
# Основной цикл игры
i = 2  # Указатель на текущую позицию в массиве входных данных
while i < len(data):
    x, y = int(data[i]), int(data[i+1])
    if x == -1 and y == -1:
        break  # Завершаем игру
    x -= 1  # Приводим к индексации от 0
    y -= 1  # Приводим к индексации от 0
    
    if turn:
        place_stone(x, y, 'white')  # Ход Стёпы
    else:
        place_stone(x, y, 'black')  # Ход Гены
    
    # Подсчитываем разницу и выводим результат
    difference = score_stepa - score_gena
    output(f"{difference}\n")
    flush()
    
    # Меняем ход
    turn = not turn
    i += 2  # Переходим к следующей паре координат

Объяснение кода

• Инициализация: создаем пустое поле и переменные для счёта камней каждого игрока.
• Функция place_stone: внутри этой функции реализуется логика добавления камня на поле, заполнение промежутков и удаление камней противника. Здесь необходимо обновлять переменные score_stepa и score_gena при каждом изменении поля.
• Цикл обработки ходов: каждый ход считывается, после чего программа определяет, какой игрок ходит, обновляет поле, подсчитывает разницу в камнях и выводит её.
• Проверка конца игры: при получении координат $(-1, -1)$ программа завершает цикл и останавливается.

Заключение

Решение требует аккуратного подхода к обновлению поля и эффективного подсчета разницы в камнях.