結果

問題 No.261 ぐるぐるぐるぐる！あみだくじ！
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:51:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 58 ms / 5,000 ms
コード長 4,033 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 69,064 KB
最終ジャッジ日時 2025-03-20 20:51:59
合計ジャッジ時間 3,355 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import gcd

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 crt(congruences):
    x, mod = 0, 1
    for a, m in congruences:
        g, p, q = extended_gcd(mod, m)
        if (a - x) % g != 0:
            return (0, 0)
        lcm = mod // g * m
        tmp = (( (a - x) // g * p ) % (m // g)) * mod
        x += tmp
        mod = lcm
        x %= mod
    return (x, mod)

def compute_p(N, swaps):
    perm = list(range(N))
    for j in range(N):
        pos = j
        for (x, y) in swaps:
            if pos == x:
                pos = y
            elif pos == y:
                pos = x
        perm[j] = pos
    return perm

def find_cycles(perm):
    visited = [False] * len(perm)
    cycles = []
    for i in range(len(perm)):
        if not visited[i]:
            cycle = []
            current = i
            while not visited[current]:
                visited[current] = True
                cycle.append(current)
                current = perm[current]
            cycles.append(cycle)
    return cycles

def array_to_perm(A):
    perm = [0] * len(A)
    for i in range(len(A)):
        val = A[i]
        perm[val - 1] = i  # val-1 is 0-based, perm[val-1] is the index i where val is located
    return perm

def compose(p1, p2):
    # compute p1 after p2: p1[p2[x]]
    return [ p1[x] for x in p2 ]

def permutation_power(perm, t):
    N = len(perm)
    result = list(range(N))
    current = perm.copy()
    while t > 0:
        if t % 2 == 1:
            result = compose(result, current)
        current = compose(current, current)
        t = t // 2
    return result

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    K = int(input[ptr])
    ptr +=1
    swaps = []
    for _ in range(K):
        X = int(input[ptr]) -1
        Y = int(input[ptr+1]) -1
        ptr +=2
        swaps.append( (X, Y) )
    perm_p = compute_p(N, swaps)
    cycles_p = find_cycles(perm_p)
    Q = int(input[ptr])
    ptr +=1
    for _ in range(Q):
        A = list(map(int, input[ptr:ptr+N]))
        ptr +=N
        perm_q = array_to_perm(A)
        valid = True
        congruences = []
        for cycle in cycles_p:
            L = len(cycle)
            cycle_set = set(cycle)
            for x in cycle:
                current = x
                visited = set()
                while True:
                    if current not in cycle_set:
                        valid = False
                        break
                    if current in visited:
                        valid = False
                        break
                    visited.add(current)
                    current = perm_q[current]
                    if current == x:
                        break
                if not valid:
                    break
            if not valid:
                break
            index_in_cycle = {x:i for i, x in enumerate(cycle)}
            s = None
            x0 = cycle[0]
            q_x0 = perm_q[x0]
            pos_q_x0 = index_in_cycle.get(q_x0, -1)
            if pos_q_x0 == -1:
                valid = False
                break
            s_candidate = (pos_q_x0 - 0) % L
            for x in cycle:
                expected_pos = (index_in_cycle[x] + s_candidate) % L
                expected_x = cycle[expected_pos]
                if perm_q[x] != expected_x:
                    valid = False
                    break
            if not valid:
                break
            congruences.append( (s_candidate, L) )
        if not valid:
            print(-1)
            continue
        x, mod = crt(congruences)
        if mod == 0:
            print(-1)
            continue
        t = x if x !=0 else mod
        if t <1:
            t += mod
        p_t = permutation_power(perm_p, t)
        if p_t == perm_q:
            print(t)
        else:
            print(-1)

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