Submission #62782846

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n = int(input())
s = input()
a = [i for i in range(n) if s[i] == "1"]
# print(a)
def f(x):
    ret = 0
    for i in range(len(a)):
        ret += abs(a[i] - x)
        x += 1
    return ret
def ternary_search(f, l, r):
    while r - l > 2:
        m1 = l + (r - l) // 3
        m2 = r - (r - l) // 3
        # print(l, r, m1, m2, f(m1), f(m2))
        if f(m1) > f(m2):
            l = m1
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

n = int(input())
s = input()
a = [i for i in range(n) if s[i] == "1"]
# print(a)


def f(x):
    ret = 0
    for i in range(len(a)):
        ret += abs(a[i] - x)
        x += 1
    return ret


def ternary_search(f, l, r):
    while r - l > 2:
        m1 = l + (r - l) // 3
        m2 = r - (r - l) // 3
        # print(l, r, m1, m2, f(m1), f(m2))
        if f(m1) > f(m2):
            l = m1
        else:
            r = m2

    ret = f(l)
    for x in range(l, r + 1):
        ret = min(ret, f(x))
    return ret


print(ternary_search(f, 0, n - 1))

Submission Info

Judge Result