#835191 (PyPy3) No.186 中華風 (Easy)

提出ソース
結果

問題	No.186 中華風 (Easy)
ユーザー	ああ
提出日時	2023-01-24 03:33:03
言語	PyPy3 (7.3.15)
結果	AC
実行時間	86 ms / 2,000 ms
コード長	13,885 bytes
コンパイル時間	310 ms
コンパイル使用メモリ	82,432 KB
実行使用メモリ	72,576 KB
最終ジャッジ日時	2024-06-25 19:59:45
合計ジャッジ時間	2,794 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	71 ms 72,192 KB
testcase_01	AC	72 ms 72,192 KB
testcase_02	AC	73 ms 72,192 KB
testcase_03	AC	72 ms 72,192 KB
testcase_04	AC	86 ms 72,064 KB
testcase_05	AC	72 ms 72,036 KB
testcase_06	AC	73 ms 72,064 KB
testcase_07	AC	73 ms 72,576 KB
testcase_08	AC	72 ms 72,064 KB
testcase_09	AC	71 ms 71,808 KB
testcase_10	AC	72 ms 72,064 KB
testcase_11	AC	71 ms 72,064 KB
testcase_12	AC	71 ms 71,808 KB
testcase_13	AC	72 ms 71,808 KB
testcase_14	AC	71 ms 71,808 KB
testcase_15	AC	73 ms 72,192 KB
testcase_16	AC	73 ms 72,192 KB
testcase_17	AC	80 ms 71,936 KB
testcase_18	AC	75 ms 72,192 KB
testcase_19	AC	73 ms 72,192 KB
testcase_20	AC	73 ms 72,064 KB
testcase_21	AC	73 ms 72,064 KB
testcase_22	AC	72 ms 72,192 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
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(*y))
  exit()

r, m = crt(x, y)
if m == 0:
  print(-1)
else:
  print(r)
yukicoder

結果

テストケース

ソースコード
