結果

問題 No.1437 01 Sort
ユーザー tyawanmusityawanmusi
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

# writer
# O(N log^2 N)
#
from bisect import bisect_left, bisect_right
n = int(input())
s = input()
ans = 10**10
zero = s.count("0")
one = n-zero
if zero == 0 or zero == n:
exit(print(0))
#
out = [0]*n
if s[0] == "1":
out[0] = 1
for i in range(n-1, -1, -1):
if s[i] == "1":
out[i] = 1
else:
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)%n
sp_r = n
if sp_l == 0:
sp_l = n
ansl = 0
if 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]-1
else:
ansl = l+n-bit[ll]
ansr = 0
if l+n+one-1 < bit[ll+one-1]:
# ""
ng = -1
ok = one
while ng+1 != ok:
mid = (ng+ok)//2
if l+n+mid < bit[ll+mid]:
ok = mid
else:
ng = mid
#
flag1 = True
flag2 = False
x = l+n+ok
if x%n != 0:
x += n-(x%n)
if x <= l+n+one-1:
if l+n+ok <= bit[ll+ok] <= x:
flag2 = True
x += n
if l+n+ok <= bit[ll+ok] <= x:
flag1 = False
ansr = one-ok
ansr += flag1
ansr -= flag2
return max(ansl, ansr)
#
for l in range(n):
#
anss = (-l-one)%n
#
sp_l = (l+one)%n
sp_r = n
if sp_l == 0:
sp_l = n
#
ng = -1
ok = n
while ng+1 != ok:
mid = (ng+ok)//2
# bit[ll, ll+one) ll
#
x = l+n-mid-1
if not(sp_l <= ((x-1)%n+1) <= sp_r and out[x%n] == 0):
x += 1
ll = bisect_left(bit,x)
if f(l, ll) <= mid:
ok = mid
else:
ng = mid
ans = min(ans, anss+ok*n)
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0