結果

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

ソースコード

diff # 

import sys
import math
from collections import defaultdict

def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None
    else:
        return x % m

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

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

    # Precompute vertical positions for 2H steps
    vertical_positions = []
    current_pos = 1
    current_dir = 'down'
    for _ in range(2 * H):
        vertical_positions.append(current_pos)
        if current_dir == 'down':
            if current_pos < H:
                current_pos += 1
            else:
                current_dir = 'up'
        else:
            if current_pos > 1:
                current_pos -= 1
            else:
                current_dir = 'down'

    # Precompute horizontal positions for 2W steps
    horizontal_positions = []
    current_pos_h = 1
    current_dir_h = 'right'
    for _ in range(2 * W):
        horizontal_positions.append(current_pos_h)
        if current_dir_h == 'right':
            if current_pos_h < W:
                current_pos_h += 1
            else:
                current_dir_h = 'left'
        else:
            if current_pos_h > 1:
                current_pos_h -= 1
            else:
                current_dir_h = 'right'

    # Build vertical and horizontal dictionaries
    vertical_a = defaultdict(list)
    for a in range(2 * H):
        i = vertical_positions[a]
        vertical_a[i].append(a)
    
    horizontal_b = defaultdict(list)
    for b in range(2 * W):
        j = horizontal_positions[b]
        horizontal_b[j].append(b)

    # Prepare the grid
    grid = []
    for i in range(1, H + 1):
        row = []
        for j in range(1, W + 1):
            a_list = vertical_a.get(i, [])
            b_list = horizontal_b.get(j, [])
            count = 0
            for a in a_list:
                for b in b_list:
                    m = 2 * H
                    n = 2 * W
                    G = math.gcd(m, n)
                    if (a - b) % G != 0:
                        continue
                    m_prime = m // G
                    n_prime = n // G
                    c = (b - a) // G
                    inv = modinv(m_prime, n_prime)
                    if inv is None:
                        continue
                    k0 = (c * inv) % n_prime
                    x = a + k0 * m
                    T = (m * n) // G
                    t0 = x % T
                    if t0 < 0:
                        t0 += T
                    if t0 >= K:
                        continue
                    num = (K - 1 - t0) // T + 1
                    count += num
            row.append('#' if count % 2 == 1 else '.')
        grid.append(''.join(row))
    
    for line in grid:
        print(line)

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