結果
問題 | No.261 ぐるぐるぐるぐる!あみだくじ! |
ユーザー | vwxyz |
提出日時 | 2021-07-31 19:01:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 252 ms / 5,000 ms |
コード長 | 2,114 bytes |
コンパイル時間 | 992 ms |
コンパイル使用メモリ | 87,060 KB |
実行使用メモリ | 95,036 KB |
最終ジャッジ日時 | 2023-10-14 15:09:12 |
合計ジャッジ時間 | 12,615 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 222 ms
91,244 KB |
testcase_01 | AC | 225 ms
91,148 KB |
testcase_02 | AC | 223 ms
91,152 KB |
testcase_03 | AC | 233 ms
93,564 KB |
testcase_04 | AC | 228 ms
91,148 KB |
testcase_05 | AC | 225 ms
91,460 KB |
testcase_06 | AC | 252 ms
94,388 KB |
testcase_07 | AC | 236 ms
94,344 KB |
testcase_08 | AC | 238 ms
93,452 KB |
testcase_09 | AC | 232 ms
91,316 KB |
testcase_10 | AC | 230 ms
91,440 KB |
testcase_11 | AC | 229 ms
91,124 KB |
testcase_12 | AC | 231 ms
91,276 KB |
testcase_13 | AC | 237 ms
93,212 KB |
testcase_14 | AC | 245 ms
94,452 KB |
testcase_15 | AC | 245 ms
94,876 KB |
testcase_16 | AC | 242 ms
94,416 KB |
testcase_17 | AC | 238 ms
94,260 KB |
testcase_18 | AC | 244 ms
94,800 KB |
testcase_19 | AC | 245 ms
94,708 KB |
testcase_20 | AC | 242 ms
94,816 KB |
testcase_21 | AC | 237 ms
94,440 KB |
testcase_22 | AC | 240 ms
94,564 KB |
testcase_23 | AC | 242 ms
94,736 KB |
testcase_24 | AC | 242 ms
93,768 KB |
testcase_25 | AC | 241 ms
94,508 KB |
testcase_26 | AC | 240 ms
94,136 KB |
testcase_27 | AC | 239 ms
94,780 KB |
testcase_28 | AC | 239 ms
94,476 KB |
testcase_29 | AC | 240 ms
94,784 KB |
testcase_30 | AC | 239 ms
95,036 KB |
testcase_31 | AC | 237 ms
94,644 KB |
testcase_32 | AC | 244 ms
94,696 KB |
testcase_33 | AC | 241 ms
94,992 KB |
testcase_34 | AC | 241 ms
94,728 KB |
testcase_35 | AC | 238 ms
94,912 KB |
testcase_36 | AC | 239 ms
94,684 KB |
testcase_37 | AC | 238 ms
94,408 KB |
testcase_38 | AC | 241 ms
94,668 KB |
testcase_39 | AC | 242 ms
94,604 KB |
ソースコード
import bisect import copy import decimal import fractions import heapq import itertools import math import random import sys from collections import Counter,deque,defaultdict from functools import lru_cache,reduce from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max def _heappush_max(heap,item): heap.append(item) heapq._siftdown_max(heap, 0, len(heap)-1) def _heappushpop_max(heap, item): if heap and item < heap[0]: item, heap[0] = heap[0], item heapq._siftup_max(heap, 0) return item from math import gcd as GCD, modf read=sys.stdin.read readline=sys.stdin.readline readlines=sys.stdin.readlines def LCM(n,m): if n or m: return abs(n)*abs(m)//math.gcd(n,m) return 0 def CRT(lst_r,lst_m): r,m=lst_r[0],lst_m[0] for r0,m0 in zip(lst_r[1:],lst_m[1:]): if (r0,m0)==(-1,0): r,m=-1,0 break r0%=m0 g=math.gcd(m,m0) l=LCM(m,m0) if r%g!=r0%g: r,m=-1,0 break r,m=(r0+m0*(((r-r0)//g)*Extended_Euclid(m0//g,m//g)[0]%(m//g)))%l,l return r,m def Extended_Euclid(n,m): stack=[] while m: stack.append((n,m)) n,m=m,n%m if n>=0: x,y=1,0 else: x,y=-1,0 for i in range(len(stack)-1,-1,-1): n,m=stack[i] x,y=y,x-(n//m)*y return x,y N=int(readline()) K=int(readline()) lst=[i for i in range(N)] for _ in range(K): X,Y=map(int,readline().split()) X-=1;Y-=1 lst[X],lst[Y]=lst[Y],lst[X] dct=[{} for i in range(N)] cycle=[None]*N for i in range(N): ii=i cnt=0 while not ii in dct[i]: dct[i][ii]=cnt ii=lst[ii] cnt+=1 cycle[i]=cnt Q=int(readline()) for _ in range(Q): A=list(map(int,readline().split())) A=[a-1 for a in A] lst_r=[] lst_m=[] for i in range(N): if A[i] in dct[i]: lst_r.append(dct[i][A[i]]) lst_m.append(cycle[i]) else: ans=-1 break else: ans,m=CRT(lst_r,lst_m) if ans==0: ans=m print(ans)