結果
問題 | No.930 数列圧縮 |
ユーザー |
![]() |
提出日時 | 2019-11-22 22:16:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 201 ms / 2,000 ms |
コード長 | 1,881 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 95,008 KB |
最終ジャッジ日時 | 2024-10-11 03:58:00 |
合計ジャッジ時間 | 4,451 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
class Bit:def __init__(self, n):self.size = nself.tree = [0] * (n + 1)def sum(self, i):s = 0while i > 0:s += self.tree[i]i -= i & -ireturn sdef add(self, i, x):while i <= self.size:self.tree[i] += xi += i & -i# i+1番目からR番目まで足すとt以上となるような最小のRを返すdef bisect_plus(self, i, t):L = iR = self.sizeR_prev = Rsum_i = self.sum(i)while True:range_sum = self.sum(R) - sum_iif range_sum < t:if R == self.size:return self.size + 1L, R = R, R_prevelse:R_prev = RR = (L + R + 1) // 2if R == R_prev:return R# L番目からi-1番目まで足すとt以上となるような最小のLを返すdef bisect_minus(self, i, t):L = 1R = iL_prev = Lsum_i = self.sum(i - 1)while True:range_sum = sum_i - self.sum(L - 1)if range_sum < t:if L == 1:return 0L, R = L_prev, Lelse:L_prev = LL = (L + R) // 2if L == L_prev:return LN = int(input())A = list(map(int, input().split()))seen = Bit(N)pos = {}for i, a in enumerate(A):seen.add(a, 1)pos[a] = i+1ans = []for i in range(1, N):if seen.sum(pos[i]) == 1:for j in range(N):if A[j] > i:ans.append(A[j])breakelif seen.sum(N) - seen.sum(pos[i]) == 0:print('No')exit()else:ans.append(i)seen.add(pos[i], -1)print('Yes')print(*ans)