結果

問題 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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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
#==========
#
# HW
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-indexn)
def genfib(n, m): # m == 0modm == 1md1mod, m == 2md2mod
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(0n)
def powtable(x, n, m): # modm = 0
md = m
if m == 1: # m == 1md1mod
md = md1
elif m == 2: # m == 2md2mod
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
# idxx
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
# ==========
#
# 1NN
# iP_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)))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0