結果
問題 | No.261 ぐるぐるぐるぐる!あみだくじ! |
ユーザー | shotoyoo |
提出日時 | 2021-06-14 22:47:00 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 113 ms / 5,000 ms |
コード長 | 3,267 bytes |
コンパイル時間 | 390 ms |
コンパイル使用メモリ | 87,112 KB |
実行使用メモリ | 77,548 KB |
最終ジャッジ日時 | 2023-08-26 09:07:05 |
合計ジャッジ時間 | 6,823 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 83 ms
71,652 KB |
testcase_01 | AC | 82 ms
71,616 KB |
testcase_02 | AC | 83 ms
71,328 KB |
testcase_03 | AC | 98 ms
76,452 KB |
testcase_04 | AC | 113 ms
76,660 KB |
testcase_05 | AC | 91 ms
76,760 KB |
testcase_06 | AC | 93 ms
76,676 KB |
testcase_07 | AC | 97 ms
76,764 KB |
testcase_08 | AC | 93 ms
76,796 KB |
testcase_09 | AC | 91 ms
76,472 KB |
testcase_10 | AC | 93 ms
77,032 KB |
testcase_11 | AC | 97 ms
76,872 KB |
testcase_12 | AC | 97 ms
76,988 KB |
testcase_13 | AC | 93 ms
77,008 KB |
testcase_14 | AC | 104 ms
77,436 KB |
testcase_15 | AC | 98 ms
77,096 KB |
testcase_16 | AC | 102 ms
77,296 KB |
testcase_17 | AC | 101 ms
77,452 KB |
testcase_18 | AC | 101 ms
77,208 KB |
testcase_19 | AC | 101 ms
77,328 KB |
testcase_20 | AC | 102 ms
77,028 KB |
testcase_21 | AC | 101 ms
77,412 KB |
testcase_22 | AC | 103 ms
77,416 KB |
testcase_23 | AC | 104 ms
77,076 KB |
testcase_24 | AC | 107 ms
77,108 KB |
testcase_25 | AC | 109 ms
77,416 KB |
testcase_26 | AC | 107 ms
77,340 KB |
testcase_27 | AC | 100 ms
77,488 KB |
testcase_28 | AC | 102 ms
77,104 KB |
testcase_29 | AC | 104 ms
77,548 KB |
testcase_30 | AC | 106 ms
77,116 KB |
testcase_31 | AC | 99 ms
77,388 KB |
testcase_32 | AC | 101 ms
77,404 KB |
testcase_33 | AC | 99 ms
77,196 KB |
testcase_34 | AC | 101 ms
77,232 KB |
testcase_35 | AC | 95 ms
77,468 KB |
testcase_36 | AC | 99 ms
77,284 KB |
testcase_37 | AC | 96 ms
76,524 KB |
testcase_38 | AC | 96 ms
76,740 KB |
testcase_39 | AC | 96 ms
76,788 KB |
ソースコード
import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(2*10**5+10) write = lambda x: sys.stdout.write(x+"\n") debug = lambda x: sys.stderr.write(x+"\n") writef = lambda x: print("{:.12f}".format(x)) def part(p): n = len(p) done = [0]*n ans = [] for i in range(n): if done[i]: continue l = [i] i0 = i done[i] = 1 while p[i]!=i0: i = p[i] l.append(i) done[i] = 1 ans.append(l) return ans def gcd2(a, b): """a*x + b*y = gcd(a,b)なるx,yも求める """ l = [] while b: l.append(divmod(a,b)) a, b = b, a%b x, y = 1, 0 for aa,bb in l[::-1]: x, y = y, x - aa*y return a, x, y def modinv(x, M): """素数ではないM、Mと互いに素なxに対し x * y == 1 mod M なるyを求める """ a,xx,yy = gcd2(x,M) return a,xx%M def solve(a,b,n): """a*x = b mod nを解く """ g,xx,yy = gcd2(a,n) if b%g!=0: return None a //= g n //= g b //= g # aとnが互いに素になっているので ainv = modinv(a, n)[1] x = ainv*b%n return x def crt(rs, ms): """中国剰余定理 x == rs[i] mod ms[i] をみたすxをを求め、(x, l(=ms))を返す (そのようなxは x + i * lとして書ける) 存在しない場合はNoneを返す 長さが0の配列を渡すと(0,1)を返す """ r0 = 0 m0 = 1 for r1,m1 in zip(rs, ms): if m0<m1: m0, m1 = m1, m0 r0, r1 = r1, r0 if m0%m1==0: if r0%m1 != r1: return None,None else: continue # print(m0,m1) g,im = modinv(m0, m1) u1 = m1//g if (r1-r0)%g!=0: return None,None x = (r1-r0) // g % u1 * im % u1 r0 += x * m0 m0 *= u1 if r0<0: r0 += m0 return r0,m0 n = int(input()) k = int(input()) p = list(range(n)) ps = [list(range(n))] for i in range(k): x,y = list(map(int, input().split())) x -= 1 y -= 1 p[x],p[y] = p[y], p[x] ps.append(p[:]) for i in range(100): ps.append([p[i] for i in ps[-1]]) res = part(p) s = [set(item) for item in res] m = len(res) g = [-1]*n for i,item in enumerate(res): for v in item: g[v] = i q = int(input()) ans = [] from collections import deque for i in range(q): a = list(map(lambda i: int(i)-1, input().split())) l = [[] for _ in range(m)] for j in range(n): l[g[j]].append(a[j]) ms = [] rs = [] for j in range(m): v = l[j][0] if v not in res[j]: ans.append(-1) break index = [jj for jj in range(n) if g[jj]==j] for ind in range(100): tmp = [ps[ind][jj] for jj in index] if tmp==l[j]: break else: ans.append(-1) break rs.append(ind) ms.append(len(res[j])) else: r0, m0 = crt(rs, ms) if r0 is None: ans.append("-1") else: val = r0%m0 if val==0: val = m0 ans.append(val) # break write("\n".join(map(str, ans)))