結果
| 問題 | No.3588 Already Ready |
| コンテスト | |
| ユーザー |
 marc2825
|
| 提出日時 | 2026-06-13 23:46:07 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 463 ms / 3,000 ms |
| コード長 | 6,748 bytes |
| 記録 | |
| コンパイル時間 | 234 ms |
| コンパイル使用メモリ | 96,236 KB |
| 実行使用メモリ | 158,464 KB |
| 最終ジャッジ日時 | 2026-07-10 21:02:42 |
| 合計ジャッジ時間 | 9,497 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 69 |
ソースコード
import sys
class LazyMinSeg:
"""range-add / range-min + 最左の値<=0 探索"""
def __init__(self, arr):
n = len(arr)
self.n = n
log = 0
while (1 << log) < n:
log += 1
self.log = log
size = 1 << log
self.size = size
BIG = float('inf')
self.d = [BIG] * (2 * size)
self.lz = [0] * size
for i in range(n):
self.d[size + i] = arr[i]
for i in range(size - 1, 0, -1):
self.d[i] = min(self.d[2*i], self.d[2*i+1])
def _all_apply(self, k, f):
self.d[k] += f
if k < self.size:
self.lz[k] += f
def _push(self, k):
v = self.lz[k]
if v != 0:
self._all_apply(2*k, v)
self._all_apply(2*k+1, v)
self.lz[k] = 0
def _update(self, k):
self.d[k] = min(self.d[2*k], self.d[2*k+1])
def apply(self, l, r, f): # [l, r) に f を加算
if l >= r:
return
size = self.size; log = self.log
l += size; r += size
for i in range(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, log+1):
if ((l >> i) << i) != l: self._update(l >> i)
if ((r >> i) << i) != r: self._update((r-1) >> i)
def first_le0(self, l, r): # [l, r) で値<=0 の最左 index（無ければ -1）
if l >= r:
return -1
size = self.size; log = self.log
l += size; r += size
for i in range(log, 0, -1):
if ((l >> i) << i) != l: self._push(l >> i)
if ((r >> i) << i) != r: self._push((r-1) >> i)
left_segs = []; right_segs = []
ll, rr = l, r
while ll < rr:
if ll & 1:
left_segs.append(ll); ll += 1
if rr & 1:
rr -= 1; right_segs.append(rr)
ll >>= 1; rr >>= 1
segs = left_segs + right_segs[::-1]
for seg in segs:
if self.d[seg] <= 0:
node = seg
while node < size:
self._push(node)
if self.d[2*node] <= 0:
node = 2*node
else:
node = 2*node + 1
return node - size
return -1
class MinSeg:
"""点更新 / 範囲最小（締切ごとの最小チーム番号）"""
def __init__(self, n, INF):
self.n = n
sz = 1
while sz < n:
sz <<= 1
self.sz = sz
self.INF = INF
self.t = [INF] * (2 * sz)
def build(self, arr):
for i in range(self.n):
self.t[self.sz + i] = arr[i]
for i in range(self.sz - 1, 0, -1):
self.t[i] = min(self.t[2*i], self.t[2*i+1])
def update(self, pos, val):
i = self.sz + pos
self.t[i] = val
i >>= 1
while i:
self.t[i] = min(self.t[2*i], self.t[2*i+1])
i >>= 1
def query(self, l, r): # [l, r) 最小
res = self.INF
l += self.sz; r += self.sz
while l < r:
if l & 1: res = min(res, self.t[l]); l += 1
if r & 1: r -= 1; res = min(res, self.t[r])
l >>= 1; r >>= 1
return res
def solve(N, K, M, A):
S = sum(A[1:])
if S % (N+1) != 0:
return None
T = S // (N+1)
if T < 1:
return None
w = [0]*(N+1)
for i in range(1, N+1):
w[i] = A[i] - T
if w[i] < 0:
return None
if w[M] < 1: # M は最終試合で勝つので前半含め1勝以上必要
return None
if A[M] - 2 < K: # 最終試合開始前に M が ready
return None
c = w[:]
c[M] -= 1 # 前半の勝利数
for i in range(1, N+1):
if c[i] > K: # 締切 U_i>=1 が必要
return None
E = T - 1 # 前半の試合数（位置 1..E）
if E == 0:
return [M]
contrib = [0]*(E+2)
groups = [[] for _ in range(K+2)] # 締切 d のチーム（番号昇順）
Uof = [0]*(N+1)
rem = [0]*(N+1)
for i in range(1, N+1):
if c[i] > 0:
U = K + 1 - c[i] # 締切
Uof[i] = U
rem[i] = c[i]
groups[U].append(i)
if U <= E:
contrib[U] += c[i]
# slack0[θ] = θ - g(θ) （g(θ)=締切<=θ のジョブ数）
slack0 = [0]*E
g = 0
for theta in range(1, E+1):
g += contrib[theta]
sl = theta - g
slack0[theta-1] = sl
if sl < 0: # Hall 条件違反
return None
treeA = LazyMinSeg(slack0)
INF_B = N + 1
leafB = [INF_B]*K
for d in range(1, K+1):
if groups[d]:
leafB[d-1] = groups[d][0]
treeB = MinSeg(K, INF_B)
treeB.build(leafB)
ptr = [0]*(K+2)
ans = []
for t in range(1, E+1):
# θ0 = t 以上で slack==0 となる最左（逼迫点）。無ければ K（制約なし）
j = treeA.first_le0(t-1, E) # 葉 [t-1, E)
theta0 = K if j == -1 else j + 1
# 締切 <= θ0 の残チームのうち最小番号
istar = treeB.query(0, theta0)
if istar >= INF_B:
return None # 起きないはず
d_star = Uof[istar]
rem[istar] -= 1
if rem[istar] == 0:
ptr[d_star] += 1
gl = groups[d_star]
nxt = gl[ptr[d_star]] if ptr[d_star] < len(gl) else INF_B
treeB.update(d_star - 1, nxt)
# 位置 t に締切 d_star のジョブを置くと、θ<d_star の slack が 1 減る
hi = min(d_star - 1, E)
if hi >= t:
treeA.apply(t-1, hi, -1) # 半開区間 [t-1, hi)
ans.append(istar)
ans.append(M)
return ans
def main():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); idx += 1
K = int(data[idx]); idx += 1
M = int(data[idx]); idx += 1
A = [0]*(N+1)
for i in range(1, N+1):
A[i] = int(data[idx]); idx += 1
res = solve(N, K, M, A)
if res is None:
sys.stdout.write("-1\n")
else:
sys.stdout.write(str(len(res)) + "\n")
sys.stdout.write(" ".join(map(str, res)) + "\n")
if __name__ == "__main__":
main()