結果

問題 No.2432 Flip and Move
ユーザー lam6er
提出日時 2025-03-31 17:40:51
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,586 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 82,668 KB
実行使用メモリ 856,844 KB
最終ジャッジ日時 2025-03-31 17:42:24
合計ジャッジ時間 4,435 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 MLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

H, W = map(int, input().split())
K = int(input())

i, j = 1, 1
ud = 'D'  # Initial vertical direction is down
lr = 'R'  # Initial horizontal direction is right

state_dict = {}  # Maps state to the step it was first encountered
pos_list = []    # Records the position flipped at each step
step = 0
found_loop = False
loop_start = 0
loop_length = 0

# Simulate steps until either K is reached or a loop is detected
while step < K:
    current_state = (i, j, ud, lr)
    if current_state in state_dict:
        # Loop detected
        prev_step = state_dict[current_state]
        loop_start = prev_step
        loop_length = step - prev_step
        found_loop = True
        break
    else:
        state_dict[current_state] = step
        pos_list.append((i, j))
        # Update position based on current directions
        # Handle vertical movement
        if ud == 'D':
            next_i = i + 1
            if next_i > H:
                ud = 'U'
            else:
                i = next_i
        else:
            next_i = i - 1
            if next_i < 1:
                ud = 'D'
            else:
                i = next_i
        # Handle horizontal movement
        if lr == 'R':
            next_j = j + 1
            if next_j > W:
                lr = 'L'
            else:
                j = next_j
        else:
            next_j = j - 1
            if next_j < 1:
                lr = 'R'
            else:
                j = next_j
        step += 1

count = {}

if found_loop:
    # Calculate flips considering the loop
    K_remaining = K - loop_start
    loop_times = K_remaining // loop_length
    remainder = K_remaining % loop_length
    loop_positions = pos_list[loop_start:]
    
    # Initial steps before the loop
    for x, y in pos_list[:loop_start]:
        count[(x, y)] = count.get((x, y), 0) + 1
    
    # Process the loop
    loop_count = {}
    for pos in loop_positions:
        loop_count[pos] = loop_count.get(pos, 0) + 1
    
    # Multiply by the number of loop iterations
    for key, val in loop_count.items():
        count[key] = count.get(key, 0) + val * loop_times
    
    # Add the remaining steps after loops
    for pos in loop_positions[:remainder]:
        count[pos] = count.get(pos, 0) + 1
else:
    # No loop found, process all steps
    for pos in pos_list:
        count[pos] = count.get(pos, 0) + 1

# Generate the output grid
for row in range(1, H + 1):
    line = []
    for col in range(1, W + 1):
        flips = count.get((row, col), 0)
        line.append('#' if flips % 2 == 1 else '.')
    print(''.join(line))
0