結果
問題 | No.202 1円玉投げ |
ユーザー |
|
提出日時 | 2025-01-25 15:21:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 4,158 ms / 5,000 ms |
コード長 | 12,785 bytes |
コンパイル時間 | 361 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 95,744 KB |
最終ジャッジ日時 | 2025-01-25 15:23:00 |
合計ジャッジ時間 | 72,624 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge7 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
# import pypyjit# pypyjit.set_param('max_unroll_recursion=-1')from collections import *from functools import *from heapq import *from itertools import *import sys, math,random# input = sys.stdin.buffer.readline# sys.setrecursionlimit(10**6)def cle(a, D):"""Counts the number of elements in D that are less than or equal to a.Parameters:a (int): The value to compare against.D (list): A sorted list of integers.Returns:int: The count of elements in D that are less than or equal to a."""y = len(D) - 1x = 0if D[x] > a:return 0if D[y] <= a:return y + 1while y - x > 1:mid = (y + x) // 2if D[mid] <= a:x = midelse:y = midreturn yclass cs_2d:"""2D cumulative sum class."""def __init__(self, x):"""Initializes the 2D cumulative sum array.Parameters:x (list of list of int): A 2D list of integers."""n = len(x)m = len(x[0])self.n = nself.m = mtmp = [0] * ((n + 1) * (m + 1))for i in range(n):for j in range(m):tmp[m * (i + 1) + j + 1] = (tmp[m * (i + 1) + j] + tmp[m * i + j + 1] - tmp[m * i + j] + x[i][j])self.S = tmpdef query(self, ix, jx, iy, jy):"""Queries the sum of the submatrix from (ix, iy) to (jx, jy).Parameters:ix (int): Starting row index.jx (int): Ending row index.iy (int): Starting column index.jy (int): Ending column index.Returns:int: The sum of the submatrix."""return (self.S[self.m * jx + jy]- self.S[self.m * jx + iy]- self.S[self.m * ix + jy]+ self.S[self.m * ix + iy])class prime_factorize:"""Class for prime factorization and related operations."""def __init__(self, M=10**6):"""Initializes the sieve for prime factorization.Parameters:M (int): The maximum number to factorize."""self.sieve = [-1] * (M + 1)self.sieve[1] = 1self.p = [False] * (M + 1)self.mu = [1] * (M + 1)for i in range(2, M + 1):if self.sieve[i] == -1:self.p[i] = Truei2 = i**2for j in range(i2, M + 1, i2):self.mu[j] = 0for j in range(i, M + 1, i):self.sieve[j] = iself.mu[j] *= -1def factors(self, x):"""Returns the prime factors of x.Parameters:x (int): The number to factorize.Returns:list: A list of prime factors of x."""tmp = []while self.sieve[x] != x:tmp.append(self.sieve[x])x //= self.sieve[x]tmp.append(self.sieve[x])return tmpdef divisors(self, x):"""Returns all divisors of x.Parameters:x (int): The number to find divisors for.Returns:list: A sorted list of all divisors of x."""if x==1:return [1]C = Counter(self.factors(x))tmp = []for p in product(*[[pow(k, i) for i in range(v + 1)] for k, v in C.items()]):res = 1for pp in p:res *= pptmp.append(res)tmp.sort()return tmpdef is_prime(self, x):"""Checks if x is a prime number.Parameters:x (int): The number to check.Returns:bool: True if x is prime, False otherwise."""return self.p[x]def mobius(self, x):"""Returns the Möbius function value of x.Parameters:x (int): The number to find the Möbius function value for.Returns:int: The Möbius function value of x."""return self.mu[x]class combination:"""Class for computing combinations (nCr) modulo p."""def __init__(self, N, p):"""Initializes the combination class.Parameters:N (int): The maximum value of n.p (int): The modulus."""self.fact = [1, 1] # fact[n] = (n! mod p)self.factinv = [1, 1] # factinv[n] = ((n!)^(-1) mod p)self.inv = [0, 1] # factinv calculationself.p = pfor i in range(2, N + 1):self.fact.append((self.fact[-1] * i) % p)self.inv.append((-self.inv[p % i] * (p // i)) % p)self.factinv.append((self.factinv[-1] * self.inv[-1]) % p)def cmb(self, n, r):"""Computes the combination (nCr) modulo p.Parameters:n (int): The total number of items.r (int): The number of items to choose.Returns:int: The value of nCr modulo p."""if (r < 0) or (n < r):return 0r = min(r, n - r)return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.pdef md(n):"""Returns all divisors of n.Parameters:n (int): The number to find divisors for.Returns:list: A sorted list of all divisors of n."""lower_divisors, upper_divisors = [], []i = 1while i * i <= n:if n % i == 0:lower_divisors.append(i)if i != n // i:upper_divisors.append(n // i)i += 1return lower_divisors + upper_divisors[::-1]class DSU:"""Disjoint Set Union (Union-Find) class."""def __init__(self, n):"""Initializes the DSU.Parameters:n (int): The number of elements."""self._n = nself.parent_or_size = [-1] * nself.member = [[i] for i in range(n)]self._max = [i for i in range(n)]self._min = [i for i in range(n)]def merge(self, a, b):"""Merges the sets containing a and b.Parameters:a (int): An element in the first set.b (int): An element in the second set.Returns:int: The leader of the merged set."""assert 0 <= a < self._nassert 0 <= b < self._nx, y = self.leader(a), self.leader(b)if x == y:return xif -self.parent_or_size[x] < -self.parent_or_size[y]:x, y = y, xself.parent_or_size[x] += self.parent_or_size[y]self._max[x] = max(self._max[x],self._max[y])self._min[x] = min(self._min[x],self._min[y])for tmp in self.member[y]:self.member[x].append(tmp)self.parent_or_size[y] = xreturn xdef get_max(self,x):return self._max[self.leader(x)]def get_min(self,x):return self._min[self.leader(x)]def members(self, a):"""Returns the members of the set containing a.Parameters:a (int): An element in the set.Returns:list: A list of members in the set containing a."""return self.member[self.leader(a)]def same(self, a, b):"""Checks if a and b are in the same set.Parameters:a (int): An element in the first set.b (int): An element in the second set.Returns:bool: True if a and b are in the same set, False otherwise."""assert 0 <= a < self._nassert 0 <= b < self._nreturn self.leader(a) == self.leader(b)def leader(self, a):"""Finds the leader of the set containing a.Parameters:a (int): An element in the set.Returns:int: The leader of the set containing a."""assert 0 <= a < self._nif self.parent_or_size[a] < 0:return aself.parent_or_size[a] = self.leader(self.parent_or_size[a])return self.parent_or_size[a]def size(self, a):"""Returns the size of the set containing a.Parameters:a (int): An element in the set.Returns:int: The size of the set containing a."""assert 0 <= a < self._nreturn -self.parent_or_size[self.leader(a)]def groups(self):"""Returns all sets as a list of lists.Returns:list: A list of lists, where each list contains the members of a set."""leader_buf = [self.leader(i) for i in range(self._n)]result = [[] for _ in range(self._n)]for i in range(self._n):result[leader_buf[i]].append(i)return [r for r in result if r != []]class SegTree:"""Segment Tree class."""def __init__(self, init_val, segfunc, ide_ele):"""Initializes the Segment Tree.Parameters:init_val (list): The initial values for the leaves of the tree.segfunc (function): The function to use for segment operations.ide_ele (any): The identity element for the segment function."""n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1 << (n - 1).bit_length()self.log = (n-1).bit_length()self.tree = [ide_ele] * 2 * self.num# Set the initial values to the leavesfor i in range(n):self.tree[self.num + i] = init_val[i]# Build the treefor i in range(self.num - 1, 0, -1):self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])def update(self, k, x):"""Updates the k-th value to x.Parameters:k (int): The index to update (0-indexed).x (any): The new value."""k += self.numself.tree[k] = xwhile k > 1:tk = k >> 1self.tree[tk] = self.segfunc(self.tree[tk << 1], self.tree[(tk << 1) + 1])k >>= 1def get(self, x):return self.tree[x + self.num]def query(self, l, r):"""Queries the segment function result for the range [l, r).Parameters:l (int): The start index (0-indexed).r (int): The end index (0-indexed).Returns:any: The result of the segment function for the range [l, r)."""res_l = self.ide_eleres_r = self.ide_elel += self.numr += self.numwhile l < r:if l & 1:res_l = self.segfunc(res_l, self.tree[l])l += 1if r & 1:res_r = self.segfunc(self.tree[r - 1], res_r)l >>= 1r >>= 1res = self.segfunc(res_l, res_r)return resclass RSQandRAQ():"""区間加算、区間取得クエリをそれぞれO(logN)で答えるadd: 区間[l, r)にvalを加えるquery: 区間[l, r)の和を求めるl, rは0-indexed"""def __init__(self, n, mod=None):self.n = nself.bit0 = [0] * (n + 1)self.bit1 = [0] * (n + 1)self.mod = moddef _add(self, bit, i, val):i = i + 1while i <= self.n:if self.mod is None:bit[i] += valelse:bit[i] = (bit[i]+val)%self.modi += i & -idef _get(self, bit, i):s = 0while i > 0:if self.mod is None:s += bit[i]else:s = (s + bit[i])%self.modi-= i & -ireturn sdef add(self, l, r, val):"""区間[l, r)にvalを加える"""self._add(self.bit0, l, -val * l)self._add(self.bit0, r, val * r)self._add(self.bit1, l, val)self._add(self.bit1, r, -val)def query(self, l, r):"""区間[l, r)の和を求める"""_res = (self._get(self.bit0, r) + r * self._get(self.bit1, r)- self._get(self.bit0, l) - l * self._get(self.bit1, l) )if self.mod is None:return _reselse:return _res%self.moddef __str__(self):return ' '.join(map(str,[self.query(i,i+1) for i in range(self.n)]))N = int(input())# ans = 0I = 30000DXY = []for i in range(-20,21):for j in range(-20,21):if i**2 + j**2 < 400:DXY.append(I*i+j)S = set()def neighbor(z):return [z+d for d in DXY]for _ in range(N):x,y = map(int,input().split())xy = I*x + yif any(z in S for z in neighbor(xy)):continueS.add(xy)print(len(S))