結果
問題 | No.2803 Bocching Star |
ユーザー |
![]() |
提出日時 | 2024-07-24 13:10:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 955 ms / 2,000 ms |
コード長 | 25,543 bytes |
コンパイル時間 | 211 ms |
コンパイル使用メモリ | 82,152 KB |
実行使用メモリ | 172,252 KB |
最終ジャッジ日時 | 2024-07-24 13:11:14 |
合計ジャッジ時間 | 24,219 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 138 ms
82,908 KB |
testcase_01 | AC | 140 ms
82,628 KB |
testcase_02 | AC | 142 ms
82,580 KB |
testcase_03 | AC | 208 ms
86,672 KB |
testcase_04 | AC | 734 ms
121,752 KB |
testcase_05 | AC | 450 ms
103,972 KB |
testcase_06 | AC | 201 ms
84,216 KB |
testcase_07 | AC | 341 ms
103,540 KB |
testcase_08 | AC | 258 ms
90,648 KB |
testcase_09 | AC | 821 ms
135,884 KB |
testcase_10 | AC | 834 ms
136,568 KB |
testcase_11 | AC | 859 ms
155,880 KB |
testcase_12 | AC | 310 ms
96,952 KB |
testcase_13 | AC | 692 ms
115,836 KB |
testcase_14 | AC | 518 ms
104,936 KB |
testcase_15 | AC | 804 ms
147,884 KB |
testcase_16 | AC | 499 ms
119,016 KB |
testcase_17 | AC | 247 ms
90,584 KB |
testcase_18 | AC | 226 ms
86,964 KB |
testcase_19 | AC | 707 ms
120,120 KB |
testcase_20 | AC | 459 ms
108,276 KB |
testcase_21 | AC | 405 ms
103,304 KB |
testcase_22 | AC | 383 ms
103,672 KB |
testcase_23 | AC | 872 ms
137,208 KB |
testcase_24 | AC | 945 ms
172,024 KB |
testcase_25 | AC | 907 ms
156,664 KB |
testcase_26 | AC | 955 ms
161,400 KB |
testcase_27 | AC | 892 ms
139,396 KB |
testcase_28 | AC | 888 ms
152,180 KB |
testcase_29 | AC | 893 ms
139,252 KB |
testcase_30 | AC | 950 ms
164,720 KB |
testcase_31 | AC | 882 ms
137,068 KB |
testcase_32 | AC | 918 ms
172,252 KB |
testcase_33 | AC | 162 ms
83,752 KB |
testcase_34 | AC | 156 ms
83,720 KB |
testcase_35 | AC | 156 ms
83,760 KB |
testcase_36 | AC | 155 ms
83,852 KB |
testcase_37 | AC | 154 ms
83,780 KB |
ソースコード
# Python3/Pypy3テンプレート集 #ライブラリ------------------------------------------------------------------- from bisect import * from heapq import * import collections from collections import deque from queue import Queue from itertools import groupby import itertools import math import array import string import copy from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN from functools import reduce from functools import cmp_to_key from operator import and_, or_, xor #便利スクリプト--------------------------------------------------------------- INF = 8*10**18 inf = 8*10**9 mod = 998244353 MOD = 10**9+7 bigmod = 8128812800000059 def YesNo(b): print("Yes") if b else print("No") def YESNO(b): print("YES") if b else print("NO") #標準入力--------------------------------------------------------------------- import sys sys.setrecursionlimit(10 ** 3 + 10000) input = sys.stdin.readline #### def int1(x): return int(x) - 1 def II(): return int(input()) def MI(): return map(int, input().split()) def MI1(): return map(int1, input().split()) def LI(): return list(map(int, input().split())) def LI1(): return list(map(int1, input().split())) def LIS(): return list(map(int, SI())) def LA(f): return list(map(f, input().split())) def LLI(rows_number): return [LI() for _ in range(rows_number)] def SI(): return input().strip('\n') def MS(): return input().split() def LS(): return list(input().strip('\n')) def LLS(rows_number): return [LS() for _ in range(rows_number)] def LMS(rows_number): return [MS() for _ in range(rows_number)] #関数------------------------------------------------------------------------ ###標準ライブラリ### def ceil(a,b): #切り捨て return (a+b-1)//b def inv(a,p): #aのpを法とする逆元(aとpは互いに素) return pow(a,p-2,p)%p def removeDuplicates_2D(A): #二次元配列の重複削除 return list(map(list, set(map(tuple, A)))) def cumulativeSum_1D(A): #配列Aの累積和 return list(itertools.accumulate(A)) def cumulativeMax_1D(A): #配列Aの累積max return list(itertools.accumulate(A, max)) def cumulativeMin_1D(A): #配列Aの累積min return list(itertools.accumulate(A, min)) def cumulativeSum_2D(S): #二次元配列Sの累積和 => 二次元リスト h = len(S) w = len(S[0]) CS = [[0 for _ in range(w)]for _ in range(h)] CCS = [[0 for _ in range(w)]for _ in range(h)] for i in range(h): for j in range(w): if(j==0): CS[i][0] = S[i][0] else: CS[i][j] = CS[i][j-1] + S[i][j] for i in range(h): for j in range(w): if(i==0): CCS[0][j] = CS[0][j] else: CCS[i][j] = CCS[i-1][j] + CS[i][j] return CCS def string_to_runLength(S: str): #文字列/リストからラングレス圧縮 grouped = groupby(S) res = [] for k, v in grouped: res.append((k, int(len(list(v))))) return res def runLength_to_string(L: "list[tuple]"): #ラングレス圧縮から文字列 => 文字だけ res = "" for c, n in L: res += c * int(n) return res def bfs(i,G): # i:始点 n = len(G) dist = [-1] * n pre = [-1] * n que = deque() dist[i] = 0 que.append(i) while not len(que)==0: v = que.popleft() for next_v in G[v]: if dist[next_v] != -1: continue dist[next_v] = dist[v] + 1 pre[next_v] = v que.append(next_v) return dist,pre def bfs01(s, G): # i:始点 => dist N = len(G) dist = [INF] * N S = deque([s]) T = deque() dist[s] = 0 d = 0 while S: while S: v = S.popleft() for c, w in G[v]: if d+c < dist[w]: dist[w] = d+c if c: T.append(w) else: S.append(w) S, T = T, S d += 1 return dist def dijkstra(s,G): #s:始点 => cost,pre | G: [(コスト,行先), ...] n = len(G) hq = [(0, s)] heapify(hq) cost = [INF]*n cost[s]= 0 pre = [-1] * n while hq: c,v = heappop(hq) if c > cost[v]: continue for d,u in G[v]: tmp = d+cost[v] if tmp < cost[u]: cost[u] = tmp pre[u] = v heappush(hq,(tmp,u)) return cost, pre def bellman_ford(s, G): # s:始点 => dist, flag(flagがTrue => -∞) | G: [(コスト,行先), ...] inf = 10 ** 18 N = len(G) dist = [inf] * N negative = [False] * N dist[s] = 0 for _ in range(N - 1): for u in range(N): if dist[u] >= inf//2: continue for c, v in G[u]: if dist[v] > dist[u] + c: dist[v] = dist[u] + c for _ in range(N): for u in range(N): if dist[u] >= inf//2: continue for c, v in G[u]: if dist[v] > dist[u] + c: negative[v] = True if negative[u]: negative[v] = True return dist, negative def coordinates(A): # 変換表(元の値 : 座標圧縮の値),変換表2(座標圧縮の値: 元の値), 圧縮後配列 B = sorted(set(A)) C = { v: i for i, v in enumerate(B) } D = { i: v for i, v in enumerate(B) } E = list(map(lambda v: C[v], A)) return C, D, E def eng_L(): return list(string.ascii_lowercase) def ENG_L(): return list(string.ascii_uppercase) def bit_len(n): #bit長 return n.bit_length() def bit_cnt(n): # bitにしたときの1の数 cnt = 0 for i in range(bit_len(n)+1): cnt += n>>i & 1 return cnt def idx_le(A, x): # x 以下の最大の要素位置 / なければ "No" return bisect_right(A, x)-1 if bisect_right(A, x)-1 != -1 else "No" def idx_lt(A, x): # x 未満の最大の要素位置 / なければ "No" return bisect_left(A, x)-1 if bisect_right(A, x)-1 != -1 else "No" def idx_ge(A, x): # x 以上の最小の要素位置 / なければ "No" return bisect_left(A, x) if bisect_left(A, x) != len(A) else "No" def idx_gt(A, x): # x 超過の最小の要素位置 / なければ "No" return bisect_right(A, x) if bisect_right(A, x) != len(A) else "No" def cnt_le(A, x): # x 以下の要素の個数 if(idx_le(A, x) == "No"): return 0 return idx_le(A, x) + 1 def cnt_lt(A, x): # x 未満の要素の個数 if(idx_lt(A, x) == "No"): return 0 return idx_lt(A, x) + 1 def cnt_ge(A, x): # x 以上の要素の個数 return len(A) - cnt_lt(A, x) def cnt_gt(A, x): # x 超過の要素の個数 return len(A) - cnt_le(A, x) ###グリッドの操作### def transpose(A): #二次元配列の転置 A_t = [] for i in range(len(A[0])) : tmp = [] for v in A : tmp.append(v[i]) A_t.append(tmp) return A_t def rotate_matrix(A): #グリッドを時計回りに90度回転 return transpose(A[::-1]) def convert(S,c): # グリッドをの 黒 マスの点集合に変換する | S: グリッド c:黒マスがなにか(ex "#",1) s = set() h = len(S) w = len(S[0]) for i in range(h): for j in range(w): if S[i][j] == c: s.add((i, j)) return s def normalize(s): # グリッドの # マスの点集合を与えると最小の x 座標と最小の y 座標がともに 0 となるように平行移動して返す if(len(s)==0): return set() mi = min(i for (i, j) in s) mj = min(j for (i, j) in s) return set((i - mi, j - mj) for (i, j) in s) def up_shift(S): #グリッドの上シフト S = S[1:] + [S[0]] return S def down_shift(S): #グリッドの下シフト S = [S[-1]] + S[:-1] return S def left_shift(S): #グリッドの左シフト h = len(S) w = len(S[0]) nS = [[0 for j in range(len(S[0]))]for i in range(len(S))] for i in range(h): for j in range(w): nS[i][j] = S[i][(j+1)%w] return nS def right_shift(S): #グリッドの右シフト h = len(S) w = len(S[0]) nS = [[0 for j in range(len(S[0]))]for i in range(len(S))] for i in range(h): for j in range(w): nS[i][j] = S[i][(j-1)%w] return nS ###数学ライブラリ### def allAND(A): # 配列Aの総AND return reduce(and_, A) def allOR(A): # 配列Aの総OR return reduce(or_, A) def allXOR(A): # 配列Aの総XOR return reduce(xor, A) def allGCD(A): # 配列Aの総GCD if(len(A)==1): return A[0] g = math.gcd(A[0],A[1]) for i in range(1,len(A)): g = math.gcd(g, A[i]) return g def mex(A): #配列Aのmexを求める B = set() for a in A: if(a>=0): B.add(a) B = list(B) B.sort() if(len(B)==0): return 0 if(B[0]!=0): return 0 m = 0 for i in range(1,len(B)): if(B[i]==B[i-1]+1): m +=1 else: break return m +1 def gcd(a,b): #aとbの最大公約数を求める return math.gcd(a,b) def lcm(a,b): #aとbの最小公倍数を求める return a*b//gcd(a,b) def extgcd(a, b): # a,b =>ax+by=gcd(a,b)を満たす(g,x,y) a,bが互いに素のとき、xはaのbを法とする逆元 if b: d, y, x = extgcd(b, a % b) y -= (a // b)*x return d, x, y return a, 1, 0 def fact_L(n,mod): # [0!, 1! ..., n!] を返す fact = [1] p = 1 for i in range(1,n+1): p *= i p %= mod fact.append(p) return fact def bitCount_L(n): # n以下のそれぞれのbitカウントを返す bitcount = [0] * (n+1) for i in range(1,n+1): bitcount[i] = bitcount[i//2] + i%2 return bitcount def factorial(n, m=0): #nの階乗 | m:mod(デフォなし) if(n<0): return -1 elif(n==0): return 1 P = 1 for i in range(1,n+1): P *= i if(m==0): continue P %= m return P def nPr(n, r, m=0): #順列nPr if(n<=0 or r<0 or n<r): return -1 if(r==0): return 1 P = 1 for i in range(n,n-r,-1): P *= i if(m==0): continue P %= m return P def nCr(n, r): #組み合わせnCr if(n<r): return 0 if(n==r): return 1 if(n<=0 or r<0 or n<r): return -1 N = 1 for i in range(r): N *= n-i R = factorial(r) return N//R def nCrm(n,r,m=mod): #逆元を用いた組み合わせnCr%mod if(n<r): return 0 if(n==r): return 1 if(n<=0 or r<0 or n<r): return -1 over=1 for i in range(n-r+1,n+1): over *= i over %= m under=1 for i in range(1,r+1): under *= i under %= m return over*pow(under,m-2,m)%m def is_prime(n): #素数判定 => True/False if n == 2: return 1 if n == 1 or n%2 == 0: return 0 m = n - 1 lsb = m & -m s = lsb.bit_length()-1 d = m // lsb test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] for a in test_numbers: if a == n: continue x = pow(a,d,n) r = 0 if x == 1: continue while x != m: x = pow(x,2,n) r += 1 if x == 1 or r == s: return 0 return 1 def prime_L(n): #n以下の素数のリスト is_prime = [True] * (n + 1) is_prime[0] = False is_prime[1] = False for i in range(2, int(n**0.5) + 1): if not is_prime[i]: continue for j in range(i * 2, n + 1, i): is_prime[j] = False return [i for i in range(n + 1) if is_prime[i]] def find_prime_factor(n): if n%2 == 0: return 2 m = int(n**0.125)+1 for c in range(1,n): f = lambda a: (pow(a,2,n)+c)%n y = 0 g = q = r = 1 k = 0 while g == 1: x = y while k < 3*r//4: y = f(y) k += 1 while k < r and g == 1: ys = y for _ in range(min(m, r-k)): y = f(y) q = q*abs(x-y)%n g = math.gcd(q,n) k += m k = r r *= 2 if g == n: g = 1 y = ys while g == 1: y = f(y) g = math.gcd(abs(x-y),n) if g == n: continue if is_prime(g): return g elif is_prime(n//g): return n//g else: return find_prime_factor(g) def primeFactorization_2L(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リスト if(n<=10**6): arr = [] temp = n for i in range(2, int(-(-n**0.5//1))+1): if temp%i==0: cnt=0 while temp%i==0: cnt+=1 temp //= i arr.append([i, cnt]) if temp!=1: arr.append([temp, 1]) if arr==[]: arr.append([n, 1]) return arr else: res = {} while not is_prime(n) and n > 1: p = find_prime_factor(n) s = 0 while n%p == 0: n //= p s += 1 res[p] = s if n > 1: res[n] = 1 R = [] for r in res: R.append([r,res[r]]) R.sort() return R def divisor_L(n): #nまでの約数のリスト if(n==1): return [1] if(n<=10**6): lower_divisors , upper_divisors = [], [] i = 1 while i*i <= n: if n % i == 0: lower_divisors.append(i) if i != n // i: upper_divisors.append(n//i) i += 1 return lower_divisors + upper_divisors[::-1] else: L = primeFactorization_2L(n) E = [[]for i in range(len(L))] for i in range(len(L)): for j in range(L[i][1]+1): E[i].append(L[i][0]**j) D = [] for p in list(itertools.product(*E)): s = 1 for v in p: s *= v D.append(s) D.sort() return D def floorsqrt(n): # N => ⌊√N⌋ # only for n <= 10 ** 18 ok = 10 ** 9 + 10 ng = 0 while ok - ng > 1: t = (ok + ng) // 2 if t * t > n: ok = t else: ng = t return ng def decimal_to_nAry(d, n): #10進数からn進数へ変換する(n<=36) |int型 => str型 if(d == 0): return "0" str_n = [] while d: if d % n >= 10: str_n.append(chr(d%n+55)) else: str_n.append(str(d%n)) d //= n return "".join(str_n[::-1]) def nAry_to_decimal(S, n): #n進数から10進数へ変換する(n<=36) | str型 => int型 num = 0 S = S.upper() S = list(S) for i in range(len(S)): if(("0"<=S[i]<="9")==False): S[i] = str(ord(S[i]) - 55) for i in range(1, len(S)+1): num += int(S[-i]) * pow(n, (i-1)) return num def roundOff(x,d): #四捨五入する x:対象の数字, d:四捨五入する位(正|負) => float型の数値 return float(Decimal(x).quantize(Decimal(f"1E{d}"), rounding=ROUND_HALF_UP)) ###幾何ライブラリ### def dsin(d): #度数法でsinを計算する return math.sin(math.radians(d)) def dcos(d): #度数法でcosを計算する return math.cos(math.radians(d)) def rotate(x,y,d,cx=0,cy=0): #P(x,y)をA(cx,cy)を中心としてに反時計回りにd°回転 => [x,y] nx = (x-cx)*dcos(d)-(y-cy)*dsin(d) ny = (x-cx)*dsin(d)+(y-cy)*dcos(d) return [nx+cx,ny+cy] def findAngle(O,A,B): #∠AOBを求める(弧度法) s = [A[0]-O[0],A[1]-O[1]] t = [B[0]-O[0],B[1]-O[1]] u = s[0]*t[0]+s[1]*t[1] l = (s[0]**2+s[1]**2)**(1/2) * (t[0]**2+t[1]**2)**(1/2) v = u/l t = math.degrees(math.acos(v)) return t def outerProduct(Av,Bv): #二次元ベクトルの外積(=符号付面積)を求める(a×b) return Av[0]*Bv[1] - Bv[0]*Av[1] def CCW(O,A,B): #Oを中心として、Aから見たAとBの位置関係を求める。 # -1: 時計回り, 0: 一直線上, 1: 反時計回り s = [A[0]-O[0],A[1]-O[1]] t = [B[0]-O[0],B[1]-O[1]] op = outerProduct(s,t) if(op > 0): return 1 if(op < 0): return -1 if(op == 0): return 0 def matrixMultiplication_2D(a,b,m=mod): #行列の掛け算(a×b) m:mod I,J,K,L = len(a),len(b[0]),len(b),len(a[0]) if(L!=K): return -1 c = [[0] * J for _ in range(I)] for i in range(I) : for j in range(J) : for k in range(K) : c[i][j] += a[i][k] * b[k][j] c[i][j] %= m return c def matrixExponentiation_2D(x,n,m=mod): #行列の累乗 (x^n) m:mod y = [[0] * len(x) for _ in range(len(x))] for i in range(len(x)): y[i][i] = 1 while n > 0: if n & 1: y = matrixMultiplication_2D(x,y,m) x = matrixMultiplication_2D(x,x,m) n >>= 1 return y def twoCircles(A,B): #二つの円の半径の位置関係 | 引数はそれぞれ[x,y(=座標),r(=半径)] # 1 : 一方の円が他方の円を完全に含み、2 つの円は接していない # 2 : 一方の円が他方の円を完全に含み、2 つの円は接している # 3 : 2 つの円が互いに交差する # 4 : 2 つの円の内部に共通部分は存在しないが、2 つの円は接している # 5 : 2 つの円の内部に共通部分は存在せず、2 つの円は接していない x1 = A[0] x2 = B[0] y1 = A[1] y2 = B[1] r1 = A[2] r2 = B[2] d = abs((x1-x2)**2 + (y1-y2)**2) if(abs(r2-r1)**2>d): return 1 elif(abs(r2-r1)**2==d): return 2 elif((r1+r2)**2>d): return 3 elif((r1+r2)**2==d): return 4 elif((r1+r2)**2<d): return 5 ###デバッグ用ライブラリ### def TS(_str): #変数/リストに格納されている値を確認 print('{}: {}'.format(_str, eval(_str))) def T2d(A): #二次元配列の確認用 for a in A: print(*a) def T3d(A): #三次元配列の確認用 for a in A: T2d(a) BR() def BR(): #横線で区切りを入れる print("---") #クラス---------------------------------------------------------------------- # UnionFind from collections import defaultdict class UnionFind(): def __init__(self, n): self.n = n self.parents = [-1] * n def find(self, x): if self.parents[x] < 0: return x else: self.parents[x] = self.find(self.parents[x]) return self.parents[x] def union(self, x, y): x = self.find(x) y = self.find(y) if x == y: return if self.parents[x] > self.parents[y]: x, y = y, x self.parents[x] += self.parents[y] self.parents[y] = x def size(self, x): return -self.parents[self.find(x)] def same(self, x, y): return self.find(x) == self.find(y) def members(self, x): root = self.find(x) return [i for i in range(self.n) if self.find(i) == root] def roots(self): return [i for i, x in enumerate(self.parents) if x < 0] def group_count(self): return len(self.roots()) def all_group_members(self): group_members = defaultdict(list) for member in range(self.n): group_members[self.find(member)].append(member) return group_members def __str__(self): return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items()) #カンニングペーパー----------------------------------------------------------- ''' ###標準ライブラリ### ceil(a,b): #切り捨て inv(a,p): #xのpを法とする逆元 | pは素数 removeDuplicates_2D(A): #二次元配列の重複削除 cumulativeSum_1D(A) #配列Aの累積和 cumulativeMax_1D(A) #配列Aの累積max cumulativeMin_1D(A) #配列Aの累積min cumulativeSum_2D(S): #二次元配列Sの累積和 => 二次元リスト string_to_runLength(S: str) #文字列/リストからラングレス圧縮 => [(文字,個数), ...]の二次元リスト runLength_to_string(L: "list[tuple]") #ラングレス圧縮 => 文字列 bfs(i,G) # i:始点 => dist,pre bfs01(i,G) # i:始点 => dist dijkstra(s,G): #s:始点 => cost,pre | G: [(コスト,行先), ...] bellman_ford(s, G): # s:始点 => dist, flag(flagがTrue => -∞) | G: [(コスト,行先), ...] coordinates(A) # 変換表(元の値 : 座標圧縮の値),変換表2(座標圧縮の値: 元の値), 圧縮後配列 eng_L() #英小文字のリスト ENG_L() #英大文字のリスト bit_len(n): #bit長 bit_cnt(n): # bitにしたときの1の数 idx_le(A, x) # x 以下の最大の要素位置 / なければ "No" idx_lt(A, x) # x 未満の最大の要素位置 / なければ "No" idx_ge(A, x) # x 以上の最小の要素位置 / なければ "No" idx_gt(A, x) # x 超過の最小の要素位置 / なければ "No" cnt_le(A, x) # x 以下の要素の個数 cnt_lt(A, x) # x 未満の要素の個数 cnt_ge(A, x) # x 以上の要素の個数 cnt_gt(A, x) # x 超過の要素の個数 ###グリッドの操作### transpose(A): # 二次元配列の転置 rotate_matrix(A): #グリッドを時計回りに90度回転 convert(S, c): # グリッドをの 黒 マスの点集合に変換する | S: グリッド c:黒マスがなにか(ex "#",1) normalize(s): # グリッドの # マスの点集合を与えると最小の x 座標と最小の y 座標がともに 0 となるように平行移動して返す ex) normalize(convert(S,c)) up_shift(S): # グリッドの上シフト down_shift(S): # グリッドの下シフト left_shift(S): # グリッドの左シフト right_shift(S): # グリッドの右シフト ###数学ライブラリ### allAND(A): # 配列Aの総AND allOR(A): # 配列Aの総OR allXOR(A): # 配列Aの総XOR allGCD(A): # 配列Aの総GCD mex(A) #配列Aのmexを求める gcd(a,b) #aとbの最大公約数を求める lcm(a,b) #aとbの最小公倍数を求める extgcd(a, b): # a,b =>ax+by=gcd(a,b)を満たす(g,x,y) a,bが互いに素のとき、xはaのbを法とする逆元 fact_L(n,mod): # [0!, 1! ..., n!] を返す bitCount_L(n): # n以下のそれぞれのbitカウントを返す factorial(n,m) #nの階乗 | m:mod(デフォなし) nPr(n,r,m) #順列nPr | m:mod(デフォなし) nCr(n,r) #組み合わせ,nCr nCrm(n,r,m) #逆元を用いた組み合わせnCr%mod divisor_L(n) #nの約数のリスト is_prime(n) #素数判定 => True/False prime_L(n) #nまでの素数のリスト primeFactorization_2L(n) #2以上の整数n => [[素因数, 指数], ...]の2次元リスト floorsqrt(n): # N => ⌊√N⌋ decimal_to_nAry(num_10,n) #10進数からn進数へ変換する(n<=36) |int型 => str型 nAry_to_decimal(num_n,n) #n進数から10進数へ変換する(n<=36) | str型 => int型 roundOff(x,d): #四捨五入する x:対象の数字, d:四捨五入する位(正|負) => float型の数値 ###幾何ライブラリ### dsin(d): #度数法でsinを計算する dcos(d): #度数法でcosを計算する rotate(x,y,d,cx,cy): #P(x,y)をA(cx,cy)を中心としてに反時計回りにd°回転(デフォ原点) => [x,y] findAngle(O,A,B) #∠AOBを求める(弧度法) | 引数はそれぞれ[x,y(=座標)] outerProduct(Av,Bv) #二次元ベクトルの外積(=符号付面積)を求める(a×b) | 引数はそれぞれ[x,y(=座標)] CCW(O,A,B) #Oを中心として、Aから見たAとBの位置関係 => -1:時計回り, 0:一直線上, 1:反時計回り | 引数はそれぞれ[x,y(=座標)] matrixMultiplication_2D(a,b,m) #行列の掛け算(a×b) m:mod | 引数は二次元リスト matrixExponentiation_2D(x,n m) #行列の累乗 (x^n) m:mod | 引数は二次元リスト twoCircles(A,B): #二つの円の半径の位置関係 | 引数はそれぞれ[x,y(=座標),r(=半径)] => 1, 2, 3, 4, 5 各数字に対応する位置関係の説明は上記参照 ###デバッグ用ライブラリ### TS(_str) # 変数/リストに格納されている値を確認 => 〇〇:×× T2d(A): # 二次元配列の確認用 T3d(A): # 三次元配列の確認用 BR() # 横線で区切りを入れる ###文法チートシート### |S|<x => "0"*(x-|S|) + S : str(n).zfill(x) 全部大文字に変換:str.upper() 全部小文字に変換:str.lower() 先頭のみ大文字に変換:str.capitalize() 各単語の先頭のみ大文字に変換(タイトルケース):str.title() 大文字と小文字を入れ替える:str.swapcase() 文字 → ASCIIコード ord(s) ASCIIコード → 文字 chr(x) ASCII表a 65:A ~ 90:Z 97:a ~ 122:z ###おまけ### le: 以下 lt: 未満 ge: 以上 gt: 超過 ''' #PyPyで再帰関数を用いる場合はコメントを外す---------------------------------- # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') #---------------------------------------------------------------------------- n,s = MI() A = LI() uf = UnionFind(n) B = [] for i in range(n): B.append([A[i], i]) B.sort() for i in range(n-1): if(B[i+1][0] - B[i][0] <= s): uf.union(i,i+1) ans = 0 G = uf.all_group_members() ans = [] for g in G: if(len(G[g]) == 1): ans.append(B[G[g][0]][1]+1) ans.sort() print(len(ans)) print(*ans)