結果

問題 No.2432 Flip and Move
ユーザー lam6er
提出日時 2025-04-16 01:05:52
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,723 bytes
コンパイル時間 249 ms
コンパイル使用メモリ 81,568 KB
実行使用メモリ 753,296 KB
最終ジャッジ日時 2025-04-16 01:07:47
合計ジャッジ時間 4,045 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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())

    current_i = 0
    current_j = 0
    v_dir = 1  # down
    h_dir = 1  # right

    path = []
    state_map = {}
    found_cycle = False
    prefix_length = 0
    cycle_length = 0

    step = 0
    while step < K:
        state = (current_i, current_j, v_dir, h_dir)
        if state in state_map:
            # Found a cycle
            prev_step = state_map[state]
            prefix_length = prev_step
            cycle_length = step - prev_step
            found_cycle = True
            break
        state_map[state] = step
        path.append((current_i, current_j))
        # Perform movement
        # Vertical movement
        new_i = current_i + v_dir
        new_v_dir = v_dir
        if new_i < 0 or new_i >= H:
            new_v_dir = -v_dir
            new_i = current_i
        # Horizontal movement
        new_j = current_j + h_dir
        new_h_dir = h_dir
        if new_j < 0 or new_j >= W:
            new_h_dir = -h_dir
            new_j = current_j
        current_i, current_j, v_dir, h_dir = new_i, new_j, new_v_dir, new_h_dir
        step += 1

    if not found_cycle:
        # All steps are in the path
        counts = defaultdict(int)
        for i, j in path:
            counts[(i, j)] += 1
        grid = []
        for i in range(H):
            row = []
            for j in range(W):
                row.append('#' if counts.get((i, j), 0) % 2 else '.')
            grid.append(''.join(row))
        print('\n'.join(grid))
    else:
        # Compute using cycle
        cycle_start = prefix_length
        cycle = path[cycle_start:cycle_start + cycle_length]
        remaining_steps = K - len(path)
        full_cycles = remaining_steps // cycle_length
        rem = remaining_steps % cycle_length

        # Compute prefix counts
        prefix_counts = defaultdict(int)
        for i, j in path[:prefix_length]:
            prefix_counts[(i, j)] += 1

        # Compute cycle counts
        cycle_counts = defaultdict(int)
        for i, j in cycle:
            cycle_counts[(i, j)] += 1

        # Compute rem counts
        rem_counts = defaultdict(int)
        for i, j in cycle[:rem]:
            rem_counts[(i, j)] += 1

        # Build the result
        grid = []
        for i in range(H):
            row = []
            for j in range(W):
                total = prefix_counts.get((i, j), 0) + full_cycles * cycle_counts.get((i, j), 0) + rem_counts.get((i, j), 0)
                row.append('#' if total % 2 else '.')
            grid.append(''.join(row))
        print('\n'.join(grid))

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