結果
問題 | No.1508 Avoid being hit |
ユーザー |
![]() |
提出日時 | 2021-05-15 00:43:48 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,167 ms / 3,000 ms |
コード長 | 1,871 bytes |
コンパイル時間 | 268 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 59,888 KB |
最終ジャッジ日時 | 2024-10-02 07:34:12 |
合計ジャッジ時間 | 24,005 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
n, q = map(int, input().split())a = list(map(int, input().split()))b = list(map(int, input().split()))segs = [None] * (q + 1)segs[q] = [[0, 1], [n + 1, n + 2]]for i in reversed(range(q)):segs[i] = []for j in range(len(segs[i + 1])):l, r = segs[i + 1][j]if j != 0 and segs[i + 1][j - 1][1] == l:continuejcopy = jwhile jcopy != len(segs[i + 1]) - 1 and r == segs[i + 1][jcopy + 1][0]:jcopy += 1r = segs[i + 1][jcopy][1]if 0 < l < n + 1:l += 1if 1 < r < n + 2:r -= 1if l < r:segs[i].append([l, r])for j in range(len(segs[i]) - 1):if segs[i][j][1] <= a[i] < segs[i][j + 1][0]:if segs[i][j][1] == a[i]:segs[i][j][1] += 1elif a[i] + 1 == segs[i][j + 1][0]:segs[i][j + 1][0] -= 1else:segs[i].append([a[i], a[i] + 1])segs[i].sort()if a[i] == b[i]:continuefor j in range(len(segs[i]) - 1):if segs[i][j][1] <= b[i] < segs[i][j + 1][0]:if segs[i][j][1] == b[i]:segs[i][j][1] += 1elif b[i] + 1 == segs[i][j + 1][0]:segs[i][j + 1][0] -= 1else:segs[i].append([b[i], b[i] + 1])segs[i].sort()ans = []for i in range(len(segs[0]) - 1):if segs[0][i][1] != segs[0][i + 1][0]:s = segs[0][i][1]breakelse:print('NO')exit()ans.append(s)for i in range(q):for j in range(len(segs[i]) - 1):if segs[i][j][1] < segs[i][j + 1][0] and segs[i][j][1] <= s + 1 and s - 1 < segs[i][j + 1][0]:s = max(s - 1, segs[i][j][1])ans.append(s)breakelse:print('NO')exit()print('YES')for x in ans:print(x)