結果

問題 No.261 ぐるぐるぐるぐる！あみだくじ！
ユーザー roiti46roiti46
提出日時 2015-07-31 23:40:33
言語 Python2
(2.7.18)
結果
WA  
実行時間 -
コード長 1,050 bytes
コンパイル時間 42 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-17 23:27:24
合計ジャッジ時間 1,874 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 10 ms
6,816 KB
testcase_01 AC 10 ms
6,940 KB
testcase_02 AC 10 ms
6,944 KB
testcase_03 AC 10 ms
6,940 KB
testcase_04 AC 13 ms
6,944 KB
testcase_05 AC 13 ms
6,940 KB
testcase_06 AC 22 ms
6,940 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def gcd(a,b):
    while b: a,b = b,a%b
    return a

def getstep(A):
    step = [1] * N
    for i in xrange(N):
        p = s[i]
        cnt = 0
        while p != A[i] - 1:
            p = s[p]
            step[i] += 1
            cnt += 1
            if cnt > N:
                step[i] = -1
                break
    return step
    
N = int(raw_input())
K = int(raw_input())
s = range(N)
for loop in xrange(K):
    X,Y = map(int,raw_input().split())
    X -= 1; Y -= 1
    s[X],s[Y] = s[Y],s[X]

step = getstep(range(1, N + 1))
MX = reduce(lambda a,b:a*b/gcd(a,b), step)

Q = int(raw_input())
for loop in xrange(Q):
    A = map(int, raw_input().split())
    step = [1] * N
    for i in range(N):
        p = s[i]
        cnt = 0
        while p != A[i] - 1:
            p = s[p]
            step[i] += 1
            cnt += 1
            if cnt > N:
                step[i] = - 1
                break
    
    if -1 not in step:
        ans = reduce(lambda a,b:a*b/gcd(a,b), step)
        print ans if ans <= MX else -1
    else:
        print -1
0