結果
| 問題 | No.3588 Already Ready |
| コンテスト | |
| ユーザー |
 kidodesu
|
| 提出日時 | 2026-07-10 22:38:45 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,337 bytes |
| 記録 | |
| コンパイル時間 | 240 ms |
| コンパイル使用メモリ | 95,976 KB |
| 実行使用メモリ | 155,564 KB |
| 最終ジャッジ日時 | 2026-07-10 22:38:59 |
| 合計ジャッジ時間 | 10,627 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 68 WA * 1 |
ソースコード
class lazy_segtree:
def update(self, k):
self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
def all_apply(self, k, f):
self.d[k] = self.mapping(f, self.d[k])
if k < self.size:
self.lz[k] = self.composition(f, self.lz[k])
def push(self, k):
self.all_apply(2 * k, self.lz[k])
self.all_apply(2 * k + 1, self.lz[k])
self.lz[k] = self.identity
def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
self.n = len(V)
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.d = [E for i in range(2 * self.size)]
self.lz = [ID for i in range(self.size)]
self.e = E
self.op = OP
self.mapping = MAPPING
self.composition = COMPOSITION
self.identity = ID
for i in range(self.n):
self.d[self.size + i] = V[i]
for i in range(self.size - 1, 0, -1):
self.update(i)
def set(self, p, x):
assert 0 <= p and p < self.n
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
self.d[p] = x
for i in range(1, self.log + 1):
self.update(p >> i)
def get(self, p):
assert 0 <= p and p < self.n
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
return self.d[p]
def prod(self, l, r):
assert 0 <= l and l <= r and r <= self.n
if l == r:
return self.e
l += self.size
r += self.size
for i in range(self.log, 0, -1):
if ((l >> i) << i) != l:
self.push(l >> i)
if ((r >> i) << i) != r:
self.push(r >> i)
sml, smr = self.e, self.e
while l < r:
if l & 1:
sml = self.op(sml, self.d[l])
l += 1
if r & 1:
r -= 1
smr = self.op(self.d[r], smr)
l >>= 1
r >>= 1
return self.op(sml, smr)
def all_prod(self):
return self.d[1]
def apply_point(self, p, f):
assert 0 <= p and p < self.n
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
self.d[p] = self.mapping(f, self.d[p])
for i in range(1, self.log + 1):
self.update(p >> i)
def apply(self, l, r, f):
assert 0 <= l and l <= r and r <= self.n
if l == r:
return
l += self.size
r += self.size
for i in range(self.log, 0, -1):
if ((l >> i) << i) != l:
self.push(l >> i)
if ((r >> i) << i) != r:
self.push((r - 1) >> i)
l2, r2 = l, r
while l < r:
if l & 1:
self.all_apply(l, f)
l += 1
if r & 1:
r -= 1
self.all_apply(r, f)
l >>= 1
r >>= 1
l, r = l2, r2
for i in range(1, self.log + 1):
if ((l >> i) << i) != l:
self.update(l >> i)
if ((r >> i) << i) != r:
self.update((r - 1) >> i)
def max_right(self, l, g):
assert 0 <= l and l <= self.n
assert g(self.e)
if l == self.n:
return self.n
l += self.size
for i in range(self.log, 0, -1):
self.push(l >> i)
sm = self.e
while 1:
while l % 2 == 0:
l >>= 1
if not (g(self.op(sm, self.d[l]))):
while l < self.size:
self.push(l)
l = 2 * l
if g(self.op(sm, self.d[l])):
sm = self.op(sm, self.d[l])
l += 1
return l - self.size
sm = self.op(sm, self.d[l])
l += 1
if (l & -l) == l:
break
return self.n
def min_left(self, r, g):
assert 0 <= r and r <= self.n
assert g(self.e)
if r == 0:
return 0
r += self.size
for i in range(self.log, 0, -1):
self.push((r - 1) >> i)
sm = self.e
while 1:
r -= 1
while r > 1 and (r % 2):
r >>= 1
if not (g(self.op(self.d[r], sm))):
while r < self.size:
self.push(r)
r = 2 * r + 1
if g(self.op(self.d[r], sm)):
sm = self.op(self.d[r], sm)
r -= 1
return r + 1 - self.size
sm = self.op(self.d[r], sm)
if (r & -r) == r:
break
return 0
def main():
n, k = list(map(int, input().split()))
last = int(input())-1
A = list(map(lambda x: int(x)-1, input().split()))
A[last] -= 1
if A[last] < k: return []
if min(A) < 0: return []
ma = sum(A)
if ma == 0: return [last+1]
N = n+1
if ma % N: return []
cnt = ma // N
for i in range(n):
A[i] -= cnt
if A[i] < 0: return []
sa = max(A)
E = [[] for _ in range(sa+1)]
LR = [[-1, -1] for _ in range(n)]
for i in range(n):
if not A[i]: continue
E[A[i]].append(i)
F = []
for a in range(sa, 0, -1):
for now in E[a]:
LR[now][0] = len(F)
for _ in range(a):
F.append(now)
LR[now][1] = len(F)
nk = k
B = [0] * n
V = []
for i in range(cnt):
nk -= 1
if B[F[i]] > nk: return []
V.append(nk-B[F[i]])
B[F[i]] += 1
def op(a, b):
return min(a, b)
def mapp(a, b):
return a+b
def comp(a, b):
return a+b
st = lazy_segtree(V, op, 1<<60, mapp, comp, 0)
Ans = []
NG = [1] * cnt
for now in range(n):
l, r = LR[now]
for m in range(l, r):
if st.prod(0, m) == 0:
break
Ans.append(now)
st.apply(0, m, -1)
st.set(m, 1<<60)
NG[m] = 0
for i in range(cnt):
if NG[i]:
Ans.append(F[i])
Ans.append(last)
return [ans+1 for ans in Ans]
Ans = main()
if Ans:
print(len(Ans))
print(*Ans)
else:
print(-1)