結果

問題 No.3742 Re: Verse X
コンテスト
ユーザー 👑 kencho
提出日時 2026-09-03 04:55:54
言語 Python3
(3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 888 ms / 2,000 ms
+ 368µs
コード長 4,230 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 71 ms
コンパイル使用メモリ 15,744 KB
実行使用メモリ 98,940 KB
最終ジャッジ日時 2026-09-19 13:05:23
合計ジャッジ時間 17,035 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

class Basis:
    def __init__(self):
        self.pivot = {}
        self.records = []

    def add(self, value, operation):
        dependencies = []
        while value:
            bit = (value & -value).bit_length() - 1
            record = self.pivot.get(bit)
            if record is None:
                self.pivot[bit] = len(self.records)
                self.records.append((value, operation, dependencies))
                return
            value ^= self.records[record][0]
            dependencies.append(record)

    def solve(self, target):
        selected = bytearray(len(self.records))
        while target:
            bit = (target & -target).bit_length() - 1
            record = self.pivot.get(bit)
            if record is None:
                return None
            target ^= self.records[record][0]
            selected[record] ^= 1
        answer = []
        for record in range(len(self.records) - 1, -1, -1):
            if selected[record]:
                _, operation, dependencies = self.records[record]
                answer.append(operation)
                for dependency in dependencies:
                    selected[dependency] ^= 1
        return answer

def operation_mask(n, k, r, c, index=None):
    value = 0
    for x in range(-k, k + 1):
        cells = [(r + x, c + x)]
        if x:
            cells.append((r + x, c - x))
        for rr, cc in cells:
            position = rr * n + cc
            bit = position if index is None else index.get(position)
            if bit is not None:
                value ^= 1 << bit
    return value

def apply(grid, n, operation):
    k, r, c = operation
    for x in range(-k, k + 1):
        grid[(r + x) * n + c + x] ^= 1
        if x:
            grid[(r + x) * n + c - x] ^= 1

def ring(n, layer):
    low, high = layer, n - 1 - layer
    result = [(low, c) for c in range(low, high + 1)]
    result += [(r, high) for r in range(low + 1, high + 1)]
    result += [(high, c) for c in range(high - 1, low - 1, -1)]
    result += [(r, low) for r in range(high - 1, low, -1)]
    return result

def solve_small(grid, n):
    basis = Basis()
    for k in range(1, (n - 1) // 2 + 1):
        for r in range(k, n - k):
            for c in range(k, n - k):
                basis.add(operation_mask(n, k, r, c), (k, r, c))
    target = sum(value << i for i, value in enumerate(grid))
    return basis.solve(target)

def toggle(chosen, operation):
    k, r, c = operation
    cell = r * n + c
    if cell in chosen[k]: chosen[k].remove(cell)
    else: chosen[k].add(cell)

def solve_large(grid, n):
    boundary = ring(n, 0) + ring(n, 1)
    index = {r * n + c: i for i, (r, c) in enumerate(boundary)}
    basis = Basis()
    for k in range(1, 4):
        for r in range(k, n - k):
            for c in range(k, n - k):
                if r - k >= 2 and r + k <= n - 3 and c - k >= 2 and c + k <= n - 3:
                    continue
                basis.add(operation_mask(n, k, r, c, index), (k, r, c))
    target = sum(grid[r * n + c] << i for i, (r, c) in enumerate(boundary))
    boundary_operations = basis.solve(target)
    if boundary_operations is None:
        return None
    chosen = [set() for _ in range(4)]
    for operation in boundary_operations:
        toggle(chosen, operation)
        apply(grid, n, operation)
    if any(grid[r * n + c] for r, c in boundary):
        return None
    for r in range(2, n - 2):
        for c in range(2, n - 2):
            if not grid[r * n + c]: continue
            for operation in ((2, r, c), (1, r - 1, c - 1), (1, r - 1, c + 1),
                              (1, r + 1, c - 1), (1, r + 1, c + 1)):
                toggle(chosen, operation)
    answer = []
    for k in range(1, 4):
        answer.extend((k, cell // n, cell % n) for cell in sorted(chosen[k]))
    return answer if len(answer) <= 500000 else None

data = sys.stdin.buffer
n = int(data.readline())
rows = [data.readline().strip() for _ in range(n)]
grid = bytearray(cell == 35 for row in rows for cell in row)
answer = solve_small(grid, n) if n < 12 else solve_large(grid, n)
if answer is None:
    print(-1)
else:
    print(len(answer))
    print("\n".join(f"{k} {r + 1} {c + 1}" for k, r, c in answer))
0