結果
| 問題 | No.2803 Bocching Star |
| ユーザー |
 Arleen
|
| 提出日時 | 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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 60 ms
65,408 KB |
| testcase_01 | AC | 58 ms
65,340 KB |
| testcase_02 | AC | 56 ms
65,392 KB |
| testcase_03 | AC | 133 ms
82,920 KB |
| testcase_04 | AC | 321 ms
145,672 KB |
| testcase_05 | AC | 213 ms
120,384 KB |
| testcase_06 | AC | 99 ms
81,816 KB |
| testcase_07 | AC | 163 ms
104,676 KB |
| testcase_08 | AC | 111 ms
84,768 KB |
| testcase_09 | AC | 335 ms
161,156 KB |
| testcase_10 | AC | 388 ms
162,336 KB |
| testcase_11 | AC | 399 ms
157,376 KB |
| testcase_12 | AC | 177 ms
101,612 KB |
| testcase_13 | AC | 300 ms
145,940 KB |
| testcase_14 | AC | 253 ms
121,908 KB |
| testcase_15 | AC | 384 ms
153,692 KB |
| testcase_16 | AC | 264 ms
120,500 KB |
| testcase_17 | AC | 109 ms
83,600 KB |
| testcase_18 | AC | 106 ms
83,320 KB |
| testcase_19 | AC | 340 ms
145,748 KB |
| testcase_20 | AC | 228 ms
120,488 KB |
| testcase_21 | AC | 193 ms
111,152 KB |
| testcase_22 | AC | 199 ms
108,820 KB |
| testcase_23 | AC | 439 ms
163,228 KB |
| testcase_24 | AC | 441 ms
171,980 KB |
| testcase_25 | AC | 427 ms
169,692 KB |
| testcase_26 | AC | 465 ms
169,864 KB |
| testcase_27 | AC | 369 ms
163,336 KB |
| testcase_28 | AC | 457 ms
166,028 KB |
| testcase_29 | AC | 406 ms
163,752 KB |
| testcase_30 | AC | 436 ms
171,068 KB |
| testcase_31 | AC | 411 ms
163,188 KB |
| testcase_32 | AC | 428 ms
173,392 KB |
| testcase_33 | AC | 68 ms
73,172 KB |
| testcase_34 | AC | 68 ms
72,384 KB |
| testcase_35 | AC | 68 ms
72,412 KB |
| testcase_36 | AC | 67 ms
72,092 KB |
| testcase_37 | AC | 67 ms
73,640 KB |
ソースコード
import sys
import itertools
import time
import heapq
from math import radians, sin, cos, tan, sqrt, comb, pow
from math import log, log2, log10, exp
from collections import deque
from operator import mul
from functools import reduce, cmp_to_key
from random import randint, randrange
from bisect import bisect_left, bisect_right
def input():
return sys.stdin.readline().replace('\n','')
#sys.setrecursionlimit(300000)
md1 = 998244353
md2 = 10 ** 9 + 7
inf = 2 ** 31 + 1
primeset = 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, primelist
left = list(primeset)
right = deque()
start = 2
if len(left) != 0:
start = pt[-1] + 1
for i in range(start, n+1):
right.append(i)
while len(right) != 0:
flag = True
now = right.popleft()
for i in range(0, len(left)):
if now < left[i] ** 2:
break
if now % left[i] == 0:
flag = False
break
if flag:
left.append(now)
return set(left)
#==========
# 数え上げ
# 1次元数え上げ
def cntx(itr, x):
cnt = 0
for i in range(0, len(itr)):
if itr[i] == x:
cnt += 1
return cnt
# 2次元数え上げ
def twodimcntx(itr, x):
sm = 0
for 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]] = 0
dct[itr[i]] += 1
return 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]] = 0
dct[itr[i][j]] += 1
return dct
#==========
# 計算ツール
# 最大公約数
def gcd(x, y):
if x < y:
return gcd(y, x)
if x % y == 0:
return y
return 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でmod
lst = [1, 1]
if m == 0:
for i in range(1, n):
lst.append(lst[-2]+lst[-1])
else:
md = md1
if m == 2:
md = md2
for i in range(1, n):
lst.append((lst[-2]+lst[-1])%md)
return lst
# 素数一覧の初期化
def primeinit(x):
global primeset, primelist
primeset = genprimeset(x)
primelist = list(primeset)
return
# 素数判定
def isitprime(x):
if x < 2:
return False
global primeset, primelist
if len(primeset) == 0:
primeinit(int(sqrt(x))+10)
elif primelist[-1] ** 2 < x:
primeinit(int(sqrt(x))+10)
if x in primeset:
return True
for i in range(0, len(primelist)):
if x % primelist[i] == 0:
return False
return True
# 素因数分解
def factorize(x):
global primeset, primelist
if len(primeset) == 0:
primeinit(int(sqrt(x))+10)
elif primelist[-1] ** 2 < x:
primeinit(int(sqrt(x))+10)
dct = {}
now = x
for i in range(0, len(primelist)):
if x < primelist[i] ** 2:
break
while now % primelist[i] == 0:
if primelist[i] not in dct:
dct[primelist[i]] = 0
dct[primelist[i]] += 1
now //= primelist[i]
if now != 1:
dct[now] = 1
return 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:
break
if 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 = 1
for i in range(0, len(key)):
cnt *= fact[key[i]] + 1
return 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 = 0
for i in range(0, len(nm)):
sm += int(nm[i])
return sm
# bitカウント(64bitまで)
def popcount(x):
now = x
now = now - ((now >> 1) & 0x5555555555555555)
now = (now & 0x3333333333333333) + ((now >> 2) & 0x3333333333333333)
now = (now + (now >> 4)) & 0x0f0f0f0f0f0f0f0f
n = 8
for i in range(0, 3):
now += (now >> n)
n *= 2
return now & 0x0000007f
# xの累乗リスト(0乗からn乗まで)
def powtable(x, n, m): # modなしの場合はm = 0に設定する
md = m
if m == 1: # m == 1ならmd1でmod
md = md1
elif m == 2: # m == 2ならmd2でmod
md = md2
lst = [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 -> v
graph = 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 -1
yet = 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 s
lst = 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]] = inf
cur[st] = 0
dist = {}
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:
continue
dist[v] = d
lst = 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 = False
for i in range(0, len(vlist)):
root[vlist[i]] = vlist[i]
vcnt[vlist[i]] = 1
for i in range(0, len(elist)):
u = elist[i][0]
v = elist[i][1]
ur = root[u]
vr = root[v]
if ur == vr:
flag = True
else:
H = ur
L = vr
if vcnt[ur] < vcnt[vr]:
H = vr
L = ur
graph[H].add(L)
vcnt[H] += vcnt[L]
q = deque()
q.append(L)
while len(q) != 0:
now = q.popleft()
root[now] = H
lst = 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 fenwick
fenwick = []
for i in range(0, n+1):
fenwick.append(init)
return
# idx番目までの和を求める
def fwsum(idx):
sm = 0
now = idx
while now > 0:
sm += fenwick[now]
now -= -now & now
return sm
# idx番目の値にxを足す
def fwadd(idx, x):
global fenwick
now = idx
while now < len(fenwick):
fenwick[now] += x
now += -now & now
return
# 転倒数
def inversion(A):
global fenwick
initfenwick(len(A), 0)
sm = 0
for 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, Mlist
a = 10 ** 9
for 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') + 1
lst.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, Mlist
if 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]]) > 1
rule2 = False
rule3 = False
if i != 0:
if starkey[i] - starkey[i-1] <= S:
rule2 = True
if i != len(starkey) - 1:
if starkey[i+1] - starkey[i] <= S:
rule3 = True
if not (rule1 or rule2 or rule3):
ans.append(list(star[starkey[i]])[0])
ans.sort()
print(len(ans))
print(' '.join(map(str, ans)))