結果

問題 No.2432 Flip and Move
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:42:22
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,428 bytes
コンパイル時間 482 ms
コンパイル使用メモリ 81,804 KB
実行使用メモリ 843,756 KB
最終ジャッジ日時 2025-04-16 16:44:14
合計ジャッジ時間 4,284 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 MLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

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

i, j = 1, 1
v_dir = 1  # down direction (1 for down, -1 for up)
h_dir = 1  # right direction (1 for right, -1 for left)

state_map = {}
steps = []
found_cycle = False
cycle_start = 0
cycle_len = 0

step = 0

while step < K:
    current_state = (i, j, v_dir, h_dir)
    if current_state in state_map:
        # Cycle detected
        prev_step = state_map[current_state]
        cycle_start = prev_step
        cycle_len = step - prev_step
        found_cycle = True
        break
    state_map[current_state] = step
    steps.append((i, j))
    # Vertical movement
    new_i = i + v_dir
    if new_i < 1 or new_i > H:
        v_dir *= -1
    else:
        i = new_i
    # Horizontal movement
    new_j = j + h_dir
    if new_j < 1 or new_j > W:
        h_dir *= -1
    else:
        j = new_j
    step += 1

# Prepare the grid
grid = [['.' for _ in range(W)] for _ in range(H)]

if not found_cycle:
    # All steps are processed without cycle
    for (r, c) in steps[:K]:
        row = r - 1
        col = c - 1
        grid[row][col] = '#' if grid[row][col] == '.' else '.'
else:
    # Process using cycle information
    prefix_steps = steps[:cycle_start]
    cycle_steps = steps[cycle_start:cycle_start + cycle_len]
    remaining_after_prefix = K - cycle_start
    if remaining_after_prefix < 0:
        # K is less than cycle_start
        for (r, c) in steps[:K]:
            row = r - 1
            col = c - 1
            grid[row][col] = '#' if grid[row][col] == '.' else '.'
    else:
        num_cycles = remaining_after_prefix // cycle_len
        rem = remaining_after_prefix % cycle_len
        # Calculate counts
        count_p = defaultdict(int)
        for (r, c) in prefix_steps:
            count_p[(r, c)] += 1
        count_c = defaultdict(int)
        for (r, c) in cycle_steps:
            count_c[(r, c)] += 1
        count_r = defaultdict(int)
        for (r, c) in cycle_steps[:rem]:
            count_r[(r, c)] += 1
        # Update grid based on counts
        for r in range(1, H + 1):
            for c in range(1, W + 1):
                total = count_p.get((r, c), 0) + num_cycles * count_c.get((r, c), 0) + count_r.get((r, c), 0)
                if total % 2 == 1:
                    grid[r - 1][c - 1] = '#'

# Print the result
for row in grid:
    print(''.join(row))
0