結果
問題 | No.1437 01 Sort |
ユーザー |
![]() |
提出日時 | 2021-02-21 01:12:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,126 ms / 2,000 ms |
コード長 | 2,202 bytes |
コンパイル時間 | 219 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 87,432 KB |
最終ジャッジ日時 | 2024-09-19 12:22:44 |
合計ジャッジ時間 | 14,817 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
# writer 解# O(N log^2 N)# にぶたんしてくれるやつfrom bisect import bisect_left, bisect_rightn = int(input())s = input()ans = 10**10zero = s.count("0")one = n-zeroif zero == 0 or zero == n:exit(print(0))# 注意事項out = [0]*nif s[0] == "1":out[0] = 1for i in range(n-1, -1, -1):if s[i] == "1":out[i] = 1else:break# "1" である index をとりあえずいっぱい列挙bit = []for i in range(n):if s[i] == "1":bit += [i, i+n, i+n+n]bit.sort()def f(l, ll):# bit[ll, ll+one) を [l, l+one) に揃えるとき、どれだけグルグル回るか#注意事項sp_l = (l+one)%nsp_r = nif sp_l == 0:sp_l = nansl = 0if bit[ll] <= l+n:# 注意事項# ((x-1)%n+1) で 0...n-1 ではなく 1...n にするif sp_l <= ((bit[ll]-1)%n+1) <= sp_r and out[bit[ll]%n] == 0:ansl = l+n-bit[ll]-1else:ansl = l+n-bit[ll]ansr = 0if l+n+one-1 < bit[ll+one-1]:# "右側" である要素を数えるにぶたんng = -1ok = onewhile ng+1 != ok:mid = (ng+ok)//2if l+n+mid < bit[ll+mid]:ok = midelse:ng = mid# 注意事項flag1 = Trueflag2 = Falsex = l+n+okif x%n != 0:x += n-(x%n)if x <= l+n+one-1:if l+n+ok <= bit[ll+ok] <= x:flag2 = Truex += nif l+n+ok <= bit[ll+ok] <= x:flag1 = Falseansr = one-okansr += flag1ansr -= flag2return max(ansl, ansr)# 目標の区間を全探索for l in range(n):# グルグル回る以前の操作回数anss = (-l-one)%n# 注意事項sp_l = (l+one)%nsp_r = nif sp_l == 0:sp_l = n# 何回グルグル回れば揃えられるかにぶたんng = -1ok = nwhile ng+1 != ok:mid = (ng+ok)//2# 回る回数を決め打ちし、bit[ll, ll+one) の ll をできるだけ小さくする# 注意事項x = l+n-mid-1if not(sp_l <= ((x-1)%n+1) <= sp_r and out[x%n] == 0):x += 1ll = bisect_left(bit,x)if f(l, ll) <= mid:ok = midelse:ng = midans = min(ans, anss+ok*n)print(ans)