結果

問題 No.2432 Flip and Move
ユーザー lam6er
提出日時 2025-04-16 00:57:39
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,174 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 82,072 KB
実行使用メモリ 752,404 KB
最終ジャッジ日時 2025-04-16 00:58:44
合計ジャッジ時間 4,349 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 MLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    H, W = map(int, sys.stdin.readline().split())
    K = int(sys.stdin.readline())

    # Directions: vertical 0=down, 1=up; horizontal 0=right, 1=left
    state = (1, 1, 0, 0)
    flips = []
    visited = {}
    found_cycle = False
    step = 0

    while step < K:
        if state in visited and not found_cycle:
            # Cycle detected
            start = visited[state]
            cycle_length = step - start
            pre_cycle_flips = flips[:start]
            cycle_flips = flips[start:step]

            remaining = K - start
            full_cycles = remaining // cycle_length
            rem = remaining % cycle_length

            # Calculate counts
            pre_counts = defaultdict(int)
            for (i, j) in pre_cycle_flips:
                pre_counts[(i, j)] += 1

            cycle_counts = defaultdict(int)
            for (i, j) in cycle_flips:
                cycle_counts[(i, j)] += 1

            total_flips = defaultdict(int)
            for key in pre_counts:
                total_flips[key] = pre_counts[key]
            for key in cycle_counts:
                total_flips[key] += cycle_counts[key] * full_cycles
            for (i, j) in cycle_flips[:rem]:
                total_flips[(i, j)] += 1

            # Generate grid
            grid = [[False] * (W + 1) for _ in range(H + 1)]
            for (i, j) in total_flips:
                if total_flips[(i, j)] % 2 == 1:
                    grid[i][j] = True

            for i in range(1, H + 1):
                print(''.join(['#' if grid[i][j] else '.' for j in range(1, W + 1)]))
            return
        else:
            visited[state] = step
            i, j, v_dir, h_dir = state
            flips.append((i, j))

            # Vertical movement
            if v_dir == 0:
                if i + 1 <= H:
                    new_i = i + 1
                    new_v_dir = 0
                else:
                    new_i = i
                    new_v_dir = 1
            else:
                if i - 1 >= 1:
                    new_i = i - 1
                    new_v_dir = 1
                else:
                    new_i = i
                    new_v_dir = 0

            # Horizontal movement
            if h_dir == 0:
                if j + 1 <= W:
                    new_j = j + 1
                    new_h_dir = 0
                else:
                    new_j = j
                    new_h_dir = 1
            else:
                if j - 1 >= 1:
                    new_j = j - 1
                    new_h_dir = 1
                else:
                    new_j = j
                    new_h_dir = 0

            state = (new_i, new_j, new_v_dir, new_h_dir)
            step += 1

    # No cycle found within K steps
    counts = defaultdict(int)
    for (i, j) in flips:
        counts[(i, j)] += 1

    grid = [[False] * (W + 1) for _ in range(H + 1)]
    for (i, j) in counts:
        if counts[(i, j)] % 2 == 1:
            grid[i][j] = True

    for i in range(1, H + 1):
        print(''.join(['#' if grid[i][j] else '.' for j in range(1, W + 1)]))

if __name__ == "__main__":
    main()
0