結果
問題 | No.2803 Bocching Star |
ユーザー |
|
提出日時 | 2024-07-12 21:19:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 465 ms / 2,000 ms |
コード長 | 14,002 bytes |
コンパイル時間 | 190 ms |
コンパイル使用メモリ | 82,828 KB |
実行使用メモリ | 173,392 KB |
最終ジャッジ日時 | 2024-07-12 21:20:05 |
合計ジャッジ時間 | 12,103 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
import sysimport itertoolsimport timeimport heapqfrom math import radians, sin, cos, tan, sqrt, comb, powfrom math import log, log2, log10, expfrom collections import dequefrom operator import mulfrom functools import reduce, cmp_to_keyfrom random import randint, randrangefrom bisect import bisect_left, bisect_rightdef input():return sys.stdin.readline().replace('\n','')#sys.setrecursionlimit(300000)md1 = 998244353md2 = 10 ** 9 + 7inf = 2 ** 31 + 1primeset = set()primelist = []fenwick = []# 入力ツール# 1行の入力を整数のリストとして受け取るdef intlist():return list(map(int, input().split()))# 1行から複数個の整数を受け取るdef getints():return tuple(map(int, input().split()))# n行の入力を文字列のリストとして受け取るdef strtable(n):lst = []for i in range(0, n):lst.append(input())return lst# n行の入力を整数のリストとして受け取るdef inttable(n):return list(map(int, strtable(n)))# 整数のリストをn個受け取るdef intlisttable(n):lst = []for i in range(0, n):lst.append(intlist())return lst# n個のクエリを先頭だけ整数、他を文字列のリストとして受け取るdef getquery(n):lst = []for i in range(0, n):query = list(input().split())qr = int(query[0])lst.append((qr, query[1:]))return lst#==========# 生成ツール# H行W列のリスト生成def twodimlist(h, w, init): # initの値で初期化lst1 = []for i in range(0, h):lst2 = []for j in range(0, w):lst2.append(init)lst1.append(lst2)return lst1# 素数テーブルをsetとして生成def genprimeset(n): #n以下の素数を列挙global primeset, primelistleft = list(primeset)right = deque()start = 2if len(left) != 0:start = pt[-1] + 1for i in range(start, n+1):right.append(i)while len(right) != 0:flag = Truenow = right.popleft()for i in range(0, len(left)):if now < left[i] ** 2:breakif now % left[i] == 0:flag = Falsebreakif flag:left.append(now)return set(left)#==========# 数え上げ# 1次元数え上げdef cntx(itr, x):cnt = 0for i in range(0, len(itr)):if itr[i] == x:cnt += 1return cnt# 2次元数え上げdef twodimcntx(itr, x):sm = 0for i in range(0, len(itr)):sm += cntx(itr[i], x)return sm# 全要素数え上げdef allcnt(itr):dct = {}for i in range(0, len(itr)):if itr[i] not in dct:dct[itr[i]] = 0dct[itr[i]] += 1return dct# 2次元全要素数え上げdef twodimallcnt(itr, x):dct = {}for i in range(0, len(itr)):for j in range(0, len(itr[i])):if itr[i][j] not in dct:dct[itr[i][j]] = 0dct[itr[i][j]] += 1return dct#==========# 計算ツール# 最大公約数def gcd(x, y):if x < y:return gcd(y, x)if x % y == 0:return yreturn gcd(y, x%y)# 最小公倍数def lcm(x, y):g = gcd(x, y)return (x*y) // g# フィボナッチ数列(0-indexで、第n項まで生成)def genfib(n, m): # m == 0ならmodなし、m == 1ならmd1でmod, m == 2ならmd2でmodlst = [1, 1]if m == 0:for i in range(1, n):lst.append(lst[-2]+lst[-1])else:md = md1if m == 2:md = md2for i in range(1, n):lst.append((lst[-2]+lst[-1])%md)return lst# 素数一覧の初期化def primeinit(x):global primeset, primelistprimeset = genprimeset(x)primelist = list(primeset)return# 素数判定def isitprime(x):if x < 2:return Falseglobal primeset, primelistif len(primeset) == 0:primeinit(int(sqrt(x))+10)elif primelist[-1] ** 2 < x:primeinit(int(sqrt(x))+10)if x in primeset:return Truefor i in range(0, len(primelist)):if x % primelist[i] == 0:return Falsereturn True# 素因数分解def factorize(x):global primeset, primelistif len(primeset) == 0:primeinit(int(sqrt(x))+10)elif primelist[-1] ** 2 < x:primeinit(int(sqrt(x))+10)dct = {}now = xfor i in range(0, len(primelist)):if x < primelist[i] ** 2:breakwhile now % primelist[i] == 0:if primelist[i] not in dct:dct[primelist[i]] = 0dct[primelist[i]] += 1now //= primelist[i]if now != 1:dct[now] = 1return dct# Coprime判定def coprime(x, y):return gcd(x, y) == 1# 約数列挙def divisor(x):s = set()for i in range(1, x+1):if x < i ** 2:breakif x % i == 0:s.add(i)s.add(x//i)lst = sorted(list(s))return lst# 約数数え上げdef countdivisor(x):fact = factorize(x)key = list(fact.keys())cnt = 1for i in range(0, len(key)):cnt *= fact[key[i]] + 1return cnt# 大文字->小文字変換def uppertolower(c):if 'A' <= c and c <= 'Z':return chr(ord(c)+32)return c# 小文字->大文字変換def lowertoupper(c):if 'a' <= c and c <= 'z':return chr(ord(c)-32)return c# 大文字小文字相互変換def upperlower(c):newc = uppertolower(c)if c == newc:newc = lowertoupper(c)return newc# x以上の要素の個数def xormore(lst, x): # lstはソート済みにすることreturn len(lst) - bisect_left(lst, x)# xより大きい要素の個数def morethanx(lst, x): # lstはソート済みにすることreturn len(lst) - bisect_right(lst, x)# x以下の要素の個数def xorless(lst, x): # lstはソート済みにすることreturn bisect_right(lst, x)# x未満の要素の個数def lessthanx(lst, x): # lstはソート済みにすることreturn bisect_left(lst, x)# 各桁の総和def digitsum(x):nm = str(x)sm = 0for i in range(0, len(nm)):sm += int(nm[i])return sm# bitカウント(64bitまで)def popcount(x):now = xnow = now - ((now >> 1) & 0x5555555555555555)now = (now & 0x3333333333333333) + ((now >> 2) & 0x3333333333333333)now = (now + (now >> 4)) & 0x0f0f0f0f0f0f0f0fn = 8for i in range(0, 3):now += (now >> n)n *= 2return now & 0x0000007f# xの累乗リスト(0乗からn乗まで)def powtable(x, n, m): # modなしの場合はm = 0に設定するmd = mif m == 1: # m == 1ならmd1でmodmd = md1elif m == 2: # m == 2ならmd2でmodmd = md2lst = [1]for i in range(0, n):if md == 0:lst.append(lst[-1]*x)else:lst.append((lst[-1]*x)%md)return lst# ==========# グラフツール# グラフの初期化def defgraph(vlist):graph = {}for i in range(0, len(vlist)):graph[vlist[i]] = set()return graph# 重み付きグラフの初期化def defgraphw(vlist):graph = {}for i in range(0, len(vlist)):graph[vlist[i]] = {}return graph# 無向グラフ生成def undirgraph(vlist, elist): # 辺の形式は(u, v)graph = defgraph(vlist)for i in range(0, len(elist)):u = elist[i][0]v = elist[i][1]graph[u].add(v)graph[v].add(u)return graph# 重み付き無向グラフ生成def undirgraphw(vlist, elist, wdict):graph = defgraphw(vlist)for i in range(0, len(elist)):u = elist[i][0]v = elist[i][1]graph[u][v] = wdict[elist[i]]graph[v][u] = wdict[elist[i]]return graph# 有向グラフ生成def dirgraph(vlist, elist): # 辺の形式は(u, v)で、向きはu -> vgraph = defgraph(vlist)for i in range(0, len(elist)):u = elist[i][0]v = elist[i][1]graph[u].add(v)return graph# 重み付き有向グラフ生成def dirgraphw(vlist, elist, wdict):graph = defgraphw(vlist)for i in range(0, len(elist)):u = elist[i][0]v = elist[i][1]graph[u][v] = wdict[elist[i]]return graph# 重み無し最短ステップdef shortest(vlist, elist, graph, st, gl):if st not in graph or gl not in graph:return -1yet = set(vlist)q = deque()q.append((st, 0))yet.discard(st)while len(q) != 0:now = q.popleft()v = now[0]s = now[1]if v == gl:return slst = list(graph[v])for i in range(0, len(lst)):nxtv = lst[i]if nxtv in yet:yet.discard(nxtv)q.append((nxtv, s+1))return -1# ダイクストラdef dijkstra(vlist, elist, graph, st):cur = {}for i in range(0, len(vlist)):cur[vlist[i]] = infcur[st] = 0dist = {}h = []heapq.heapify(h)heapq.heappush(h, (0, st))while len(h) != 0:now = heapq.heappop(h)d = now[0]v = now[1]if v in dist:continuedist[v] = dlst = list(graph[v].keys())for i in range(0, len(lst)):nxt = lst[i]if nxt not in dist:nxtd = dist[v] + graph[v][nxt]cur[nxt] = min(cur[nxt], nxtd)if cur[nxt] == nxtd:heapq.heappush(h, (nxtd, nxt))return dist# Union-Find生成def genunionfind(vlist, elist): # 辺の形式は(u, v)graph = defgraph(vlist)root = {}vcnt = {}flag = Falsefor i in range(0, len(vlist)):root[vlist[i]] = vlist[i]vcnt[vlist[i]] = 1for i in range(0, len(elist)):u = elist[i][0]v = elist[i][1]ur = root[u]vr = root[v]if ur == vr:flag = Trueelse:H = urL = vrif vcnt[ur] < vcnt[vr]:H = vrL = urgraph[H].add(L)vcnt[H] += vcnt[L]q = deque()q.append(L)while len(q) != 0:now = q.popleft()root[now] = Hlst = list(graph[now])for j in range(0, len(lst)):q.append(lst[j])return (graph, root, vcnt, flag) # (グラフ, 根, 頂点の数, ループ検出)の形式で返す# ==========# fenwick木# fenwickを初期化def initfenwick(n, init):global fenwickfenwick = []for i in range(0, n+1):fenwick.append(init)return# idx番目までの和を求めるdef fwsum(idx):sm = 0now = idxwhile now > 0:sm += fenwick[now]now -= -now & nowreturn sm# idx番目の値にxを足すdef fwadd(idx, x):global fenwicknow = idxwhile now < len(fenwick):fenwick[now] += xnow += -now & nowreturn# 転倒数def inversion(A):global fenwickinitfenwick(len(A), 0)sm = 0for i in range(0, len(A)):sm += i - fwsum(A[i])fwadd(A[i], 1)return sm# ==========# ハッシュMset = set()Mlist = []# Mの候補の素数を生成def initM():global Mset, Mlista = 10 ** 9for i in range(-10000, 10001):if isitprime(a+i):Mset.add(a+i)Mlist = list(Mset)return# Bの累乗を生成def genB(b, m, n):lst = [1]for i in range(0, n):lst.append((lst[-1]*b)%m)return lst# ハッシュテーブル生成def genH(b, m, s):lst = [0]for i in range(0, len(s)):a = ord(s[i]) - ord('a') + 1lst.append((b*lst[-1]+a)%m)return lst# 部分文字列のハッシュ値を求めるdef Hval(Hlist, Blist, M, L, R):return (Hlist[R] - Blist[R-L+1]*Hlist[L-1]) % M# ハッシュを複数生成def multihash(s):global Mset, Mlistif len(Mlist) == 0:initM()bm = {}for i in range(0, 5):b = randint(9900, 11000)m = Mlist[randrange(0, len(Mlist))]while (b, m) in bm:b = randint(9900, 11000)m = Mlist[randrange(0, len(Mlist))]Blist = genB(b, m, len(s))Hlist = genH(b, m, s)bm[(b, m)] = (Blist, Hlist)return bm# 指定したb, mでハッシュ生成def multihashconst(s, bmkey):h = {}for i in range(0, 5):b = bmkey[i][0]m = bmkey[i][1]Blist = genB(b, m, len(s))Hlist = genH(b, m, s)h[(b, m)] = (Blist, Hlist)return h# ==========# 【問題要約】# 1からNまでの番号が付いたN個の星がある# 空は数直線とみなすことができ、星iは座標P_iにある# 同じ座標に複数個の星がある場合もある# 各星は距離S以内に別の星がないとき、またその時に限り「孤立した星」という# 孤立した星を番号の昇順に列挙せよ## 1 <= N <= 200000# 0 <= S <= 10^9# 0 <= P <= 10^9# 孤立した星は1個以上存在する# 入力はすべて整数## ==========# コードはここから書くN, S = getints()P = intlist()star = {}for i in range(0, N):if P[i] not in star:star[P[i]] = set()star[P[i]].add(i+1)starkey = list(star.keys())starkey.sort()ans = []for i in range(0, len(starkey)):rule1 = len(star[starkey[i]]) > 1rule2 = Falserule3 = Falseif i != 0:if starkey[i] - starkey[i-1] <= S:rule2 = Trueif i != len(starkey) - 1:if starkey[i+1] - starkey[i] <= S:rule3 = Trueif not (rule1 or rule2 or rule3):ans.append(list(star[starkey[i]])[0])ans.sort()print(len(ans))print(' '.join(map(str, ans)))