結果
| 問題 |
No.186 中華風 (Easy)
|
| コンテスト | |
| ユーザー |
 ああ
|
| 提出日時 | 2023-01-24 03:32:07 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,885 bytes |
| コンパイル時間 | 313 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 72,320 KB |
| 最終ジャッジ日時 | 2024-06-25 19:59:10 |
| 合計ジャッジ時間 | 3,268 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 21 WA * 2 |
ソースコード
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations, zip_longest
import itertools
import math
import operator
from sys import setrecursionlimit
import copy
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, Sequence, Tuple, TypeVar, Union, List
T = TypeVar('T')
class dsu():
n=1
parent_or_size=[-1 for i in range(n)]
def __init__(self,N):
self.n=N
self.parent_or_size=[-1 for i in range(N)]
def merge(self,a,b):
assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n)
x=self.leader(a)
y=self.leader(b)
if x==y:
return x
if (-self.parent_or_size[x]<-self.parent_or_size[y]):
x,y=y,x
self.parent_or_size[x]+=self.parent_or_size[y]
self.parent_or_size[y]=x
return x
def same(self,a,b):
assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n)
return self.leader(a)==self.leader(b)
def leader(self,a):
assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
if (self.parent_or_size[a]<0):
return a
self.parent_or_size[a]=self.leader(self.parent_or_size[a])
return self.parent_or_size[a]
def size(self,a):
assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
return -self.parent_or_size[self.leader(a)]
def groups(self):
leader_buf=[0 for i in range(self.n)]
group_size=[0 for i in range(self.n)]
for i in range(self.n):
leader_buf[i]=self.leader(i)
group_size[leader_buf[i]]+=1
result=[[] for i in range(self.n)]
for i in range(self.n):
result[leader_buf[i]].append(i)
result2=[]
for i in range(self.n):
if len(result[i])>0:
result2.append(result[i])
return result2
class multiset(Generic[T]):
BUCKET_RATIO = 50
REBUILD_RATIO = 170
def _build(self, a=None) -> None:
"Evenly divide `a` into buckets."
if a is None: a = list(self)
size = self.size = len(a)
bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
self.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]
def __init__(self, a: Iterable[T] = []) -> None:
"Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
a = list(a)
if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)): # type: ignore
a = sorted(a) # type: ignore
self._build(a)
def __iter__(self) -> Iterator[T]:
for i in self.a:
for j in i: yield j # type: ignore
def __reversed__(self) -> Iterator[T]:
for i in reversed(self.a):
for j in reversed(i): yield j
def __len__(self) -> int:
return self.size
def __repr__(self) -> str:
return "SortedMultiset" + str(self.a)
def __str__(self) -> str:
s = str(list(self))
return "{" + s[1 : len(s) - 1] + "}"
def _find_bucket(self, x: T) -> List[T]:
"Find the bucket which should contain x. self must not be empty."
for a in self.a:
if x <= a[-1]: # type: ignore
return a
return self.a[-1]
def __contains__(self, x: T) -> bool:
if self.size == 0: return False
a = self._find_bucket(x)
i = bisect_left(a, x) # type: ignore
return i != len(a) and a[i] == x
def count(self, x: T) -> int:
"Count the number of x."
return self.index_right(x) - self.index(x)
def add(self, x: T) -> None:
"Add an element. / O(√N)"
if self.size == 0:
self.a = [[x]]
self.size = 1
return
a = self._find_bucket(x)
insort(a, x)
self.size += 1
if len(a) > len(self.a) * self.REBUILD_RATIO:
self._build()
def discard(self, x: T) -> bool:
"Remove an element and return True if removed. / O(√N)"
if self.size == 0: return False
a = self._find_bucket(x)
i = bisect_left(a, x) # type: ignore
if i == len(a) or a[i] != x: return False
a.pop(i)
self.size -= 1
if len(a) == 0: self._build()
return True
def lt(self, x: T) -> Union[T, None]:
"Find the largest element < x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] < x: # type: ignore
return a[bisect_left(a, x) - 1] # type: ignore
def le(self, x: T) -> Union[T, None]:
"Find the largest element <= x, or None if it doesn't exist."
for a in reversed(self.a):
if a[0] <= x: # type: ignore
return a[bisect_right(a, x) - 1] # type: ignore
def gt(self, x: T) -> Union[T, None]:
"Find the smallest element > x, or None if it doesn't exist."
for a in self.a:
if a[-1] > x: # type: ignore
return a[bisect_right(a, x)] # type: ignore
def ge(self, x: T) -> Union[T, None]:
"Find the smallest element >= x, or None if it doesn't exist."
for a in self.a:
if a[-1] >= x: # type: ignore
return a[bisect_left(a, x)] # type: ignore
def __getitem__(self, x: int) -> T:
"Return the x-th element, or IndexError if it doesn't exist."
if x < 0: x += self.size
if x < 0: raise IndexError
for a in self.a:
if x < len(a): return a[x] # type: ignore
x -= len(a)
raise IndexError
def index(self, x: T) -> int:
"Count the number of elements < x."
ans = 0
for a in self.a:
if a[-1] >= x: # type: ignore
return ans + bisect_left(a, x) # type: ignore
ans += len(a)
return ans
def index_right(self, x: T) -> int:
"Count the number of elements <= x."
ans = 0
for a in self.a:
if a[-1] > x: # type: ignore
return ans + bisect_right(a, x) # type: ignore
ans += len(a)
return ans
class bit:
def __init__(self, n):
self._n = n
self.data = [0] * n
def add(self, p, x):
assert 0 <= p < self._n
p += 1
while p <= self._n:
self.data[p - 1] += x
p += p & -p
def sum(self, l, r)->int:
assert 0 <= l <= r <= self._n
return self._sum(r) - self._sum(l)
def _sum(self, r):
s = 0
while r > 0:
s += self.data[r - 1]
r -= r & -r
return s
class SegTree:
def __init__(self, op, e, n, v=None):
self._n = n
self._op = op
self._e = e
self._log = (n - 1).bit_length()
self._size = 1 << self._log
self._d = [self._e()] * (self._size << 1)
if v is not None:
for i in range(self._n):
self._d[self._size + i] = v[i]
for i in range(self._size - 1, 0, -1):
self._d[i] = self._op(self._d[i << 1], self._d[i << 1 | 1])
def set(self, p, x):
p += self._size
self._d[p] = x
while p:
self._d[p >> 1] = self._op(self._d[p], self._d[p ^ 1])
p >>= 1
def get(self, p):
return self._d[p + self._size]
def prod(self, l, r):
sml, smr = self._e(), self._e()
l += self._size
r += self._size
while l < r:
if l & 1:
sml = self._op(sml, self._d[l])
l += 1
if r & 1:
r -= 1
smr = self._op(self._d[r], smr)
l >>= 1
r >>= 1
return self._op(sml, smr)
def all_prod(self):
return self._d[1]
def dijkstra(g, c, s):
inf = 2 << 60
d = [inf] * len(g)
heap = [(0, s)]
heapify(heap)
while heap:
dis, u = heappop(heap)
if dis > d[u]:
continue
d[u] = dis
for v in g[u]:
if d[v] > d[u] + c[(u, v)]:
heappush(heap, (d[u] + c[(u, v)], v))
return d
def bfs(g, s):
que = deque([s])
d = [-1] * len(g)
d[s] = 0
while que:
u = que.popleft()
for v in g[u]:
if d[v] != -1:
continue
d[v] = d[u] + 1
que.append(v)
return d
def readweightedgraph(n, m):
g = [[] for _ in range(n)]
idx = {}
cost = {}
for i in range(m):
a, b, c = map(int, input().split(' '))
a -= 1
b -= 1
g[a].append(b)
g[b].append(a)
idx[(a, b)] = i
idx[(b, a)] = i
cost[(a, b)] = c
cost[(b, a)] = c
return g, idx, cost
def readdirgraph(n, m):
g = [[] for _ in range(n)]
for i in range(m):
u, v = map(int, input().split(' '))
g[u - 1].append(v - 1)
return g
def readnondirgraph(n, m):
g = [[] for _ in range(n)]
for i in range(m):
u, v = map(int, input().split(' '))
g[u - 1].append(v - 1)
g[v - 1].append(u - 1)
return g
def mycom(n, r):
if n - r < r:
return mycom(n, n - r)
return math.factorial(n) // math.factorial(r) // math.factorial(n - r)
fac = []
inv = []
finv = []
def cominit(n: int):
global fac, inv, finv
fac = [0] * (n + 1)
inv = [0] * (n + 1)
finv = [0] * (n + 1)
fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1
for i in range(2, n + 1):
fac[i] = fac[i - 1] * i % mod
inv[i] = mod - mod // i * inv[mod % i] % mod
finv[i] = finv[i - 1] * inv[i] % mod
def com(n:int, r:int):
return fac[n] * finv[r] * finv[n - r] % mod
def modpow(a, n, m):
ret = 1
while n:
if n & 1:
ret = ret * a % m
a = a * a % m
n >>= 1
return ret
def listdividers(n: int):
assert n > 0
low = []
high = []
for i in range(1, n + 1):
if i*i>n:
break
if not n % i:
q = n // i
if i == q:
low.append(i)
else:
low.append(i)
high.append(q)
return low + high[::-1]
def lcm(a:int, b:int):
return a * b // math.gcd(a, b)
def chunked(l, n: int):
for i in range(0, len(l), n):
yield l[i:i + n]
def narytoint(a:str, b:int):
ans = 0
for c in a:
ans *= b
ans += int(c)
return ans
def narytostr(a:int, b:int):
if a == 0:
return '0'
s = []
while a:
s.append(str(a%b))
a //= b
return ''.join(reversed(s))
def mulmat(a: Sequence[Sequence], b: Sequence[Sequence]):
assert len(a[0]) == len(b)
l = len(a)
m = len(a[0])
n = len(b[0])
ans = [[0] * n for _ in range(l)]
for i in range(l):
for j in range(n):
for k in range(m):
ans[i][j] += a[i][k] * b[k][j]
return ans
def applymat(a: Sequence[Sequence], b: Sequence):
pass
def xgcd(a, b):
x0, y0, x1, y1 = 1, 0, 0, 1
while b != 0:
q, a, b = a // b, b, a % b
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
return a, x0, y0
def modinv(a, m):
g, x, _ = xgcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def lcs(a: str, b:str):
n = len(a)
m = len(b)
dp = [0] * (m + 1)
for i in range(n):
nxt = [0] * (m + 1)
for j in range(m):
if a[i] == b[j]:
nxt[j+1] = dp[j] + 1
else:
nxt[j+1] = max(dp[j+1], nxt[j])
dp = nxt
return dp[m]
def pfact(n:int):
if n <= 1:
return {}
cur = n
ans = defaultdict(int)
for i in range(2,n+1):
if i*i>n:
break
while not cur % i:
cur //= i
ans[i] += 1
if cur != 1:
ans[cur] += 1
return dict(ans)
def bubblesort(x: List):
l = len(x)
for i in range(l-1):
for j in range(l-1-i):
if x[j] > x[j+1]:
x[j], x[j+1] = x[j+1], x[j]
def perm2(n, s, cur, x, r):
if len(x) == n-1:
r.append(x+[s-cur])
return
for i in range(s-cur+1):
x.append(i)
cur += i
perm2(n, s, cur, x, r)
x.pop()
cur -= i
def arithmetic_sum(a, d, n):
return n*(2*a+(n-1)*d)//2
def clamp(x, mn, mx):
return mn if x < mn else mx if mx < x else x
def isin(x, mn, mx):
return mn <= x and x < mx
def list_primes(limit):
primes = []
is_prime = [True] * (limit + 1)
is_prime[0] = False
is_prime[1] = False
for p in range (0, limit + 1):
if not is_prime[p]:
continue
primes.append(p)
for i in range(p*p, limit + 1, p):
is_prime[i] = False
return primes
def z_algorithm(s:str):
z = [0]*len(s)
i = 1
j = 0
z[0] = len(s)
while i < len(s):
while i+j < len(s) and s[i+j] == s[j]:
j += 1
z[i] = j
if j == 0:
i += 1
continue
k = 1
while k < j and k+z[k] < j:
z[i+k] = z[k]
k += 1
i += k
j -= k
return z
def exgcd(a:int, b:int):
if b == 0:
return a, 1, 0
d, y, x = exgcd(b, a%b)
y -= a//b*x
return d, x, y
# def crt(V:Sequence[Tuple[int, int]]):
# x = 0; d = 1
# for X, Y in V:
# a, b, g = exgcd(d, Y)
# x, d = (Y*b*x + d*a*X) // g, d*(Y // g)
# x %= d
# return x, d
# def crt2(b1:int, m1:int, b2:int, m2:int):
# x, y, d = exgcd(m1, m2)
# if (b2-b1) % d != 0:
# return (0, 0)
# m = m1 * (m2//d)
# tmp = (b2-b1)//d*x%(m2//d)
# r = (b1 + m1 * tmp) % m
# print(x, y, d, m, tmp, r)
# return (r, m)
def crt(r: Sequence[int], m: Sequence[int]):
x, y = 0, 1
for rr, mm in zip(r, m):
d, p, q = exgcd(y, mm)
if (rr-x) % d != 0:
return (0, 0)
tmp = (rr-x)//d*p
x += y * tmp
y *= mm//d
x %= y
return (x, y)
mod = 998244353
# mod = 10**9+7
inf = 1 << 60
setrecursionlimit(1000000)
x, y = zip(*tuple(map(int, (input().split(' '))) for _ in range(3)))
if not any(x):
print(math.lcm(*x))
exit()
r, m = crt(x, y)
if m == 0:
print(-1)
else:
print(r)