Problem p03620 (python)

Fixed submission:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#11:00

in1 = input()
in2 = input()
n = len(in1)
a,b = [],[]

for i in range(n):
    a.append(int(in1[i]))
    b.append(int(in2[i]))

if(sum(b)==0):
    if(sum(a)==0):
        print(0)
    else:
        print(-1)
    exit()

ok=1
for i in range(n):
    if(a[i]!=b[i]):
        ok=0
if(ok==1):
    print(0)
    exit()

####

left = []
rightest = -1-n
for i in range(n):
    if(b[i]==1):
        rightest = i-n

for i in range(n):
    if(b[i]==1):
        rightest = i
    left.append(rightest-i)


right = []
leftest = 2*n
for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i +n

for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i
    right.append(leftest - (n-1-i))
right = [right[n-1-i] for i in range(n)]

#print(left,right)

ans = 10**18
for i in range(n):
    toFix = [0 for i in range(n)]
    lrs = []
    for j in range(n):
        ij = (i+j)%n
        if(a[j]!=b[ij]):
            toFix[j]=1
            lrs.append([left[j],right[j]])
    lrs.sort(key = lambda x : x[0])
    #print(lrs)
    if(len(lrs)==0):
        ans = min(ans,i,n-i)
        continue
    leftmin = lrs[0][0]
    leftmax = lrs[-1][0]
    rightmin = n
    for j in lrs:
        rightmin = min(rightmin,j[1])
    
    rangemin = leftmin
    rangemax = leftmax
    for j in range(len(lrs)):
        dist = len(lrs)
        dist += abs(rangemin)
        dist += abs(rangemax-rangemin)
        dist1 = dist + abs(rangemax-i)
        dist2 = dist + abs(rangemax-(i-n))
        dist = len(lrs)
        dist += abs(rangemax)
        dist += abs(rangemax-rangemin)
        dist3 = dist + abs(rangemin-i)
        dist4 = dist + abs(rangemin-(i-n))
        #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
        ans = min(ans,dist1,dist2,dist3,dist4)

        rangemin = lrs[(j+1)%len(lrs)][0]
        rangemax = max(rangemax,lrs[j][1])
    rangemin = rightmin
    dist = len(lrs)
    dist += abs(rangemin)
    dist += abs(rangemax-rangemin)
    dist1 = dist + abs(rangemax-i)
    dist2 = dist + abs(rangemax-(i-n))
    dist = len(lrs)
    dist += abs(rangemax)
    dist += abs(rangemax-rangemin)
    dist3 = dist + abs(rangemin-i)
    dist4 = dist + abs(rangemin-(i-n))
    #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
    ans = min(ans,dist1,dist2,dist3,dist4)

    #print(i,"finish")

print(ans)

Buggy submission (verdict: Runtime Error):
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#11:00

in1 = input()
in2 = input()
n = len(in1)
a,b = [],[]

for i in range(n):
    a.append(int(in1[i]))
    b.append(int(in2[i]))

if(sum(b)==0):
    if(sum(a)==0):
        print(0)
    else:
        print(-1)
    exit()

if(a==b):
    print(0)
    exit()
    
b3 = []
for i in range(3):
    for j in range(n):
        b3.append(b[j])

####

left = []
rightest = -1-n
for i in range(n):
    if(b[i]==1):
        rightest = i-n

for i in range(n):
    if(b[i]==1):
        rightest = i
    left.append(rightest-i)


right = []
leftest = 2*n
for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i +n

for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i
    right.append(leftest - (n-1-i))
right = [right[n-1-i] for i in range(n)]

#print(left,right)

ans = 10**18
for i in range(n):
    toFix = [0 for i in range(n)]
    lrs = []
    for j in range(n):
        ij = (i+j)%n
        if(a[j]!=b[ij]):
            toFix[j]=1
            lrs.append([left[j],right[j]])
    lrs.sort(key = lambda x : x[0])
    #print(lrs)
    leftmin = lrs[0][0]
    leftmax = lrs[-1][0]
    rightmin = n
    for j in lrs:
        rightmin = min(rightmin,j[1])
    
    rangemin = leftmin
    rangemax = leftmax
    for j in range(len(lrs)):
        dist = len(lrs)
        dist += abs(rangemin)
        dist += abs(rangemax-rangemin)
        dist1 = dist + abs(rangemax-i)
        dist2 = dist + abs(rangemax-(i-n))
        dist = len(lrs)
        dist += abs(rangemax)
        dist += abs(rangemax-rangemin)
        dist3 = dist + abs(rangemin-i)
        dist4 = dist + abs(rangemin-(i-n))
        #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
        ans = min(ans,dist1,dist2,dist3,dist4)

        rangemin = lrs[(j+1)%len(lrs)][0]
        rangemax = max(rangemax,lrs[j][1])
    rangemin = rightmin
    dist = len(lrs)
    dist += abs(rangemin)
    dist += abs(rangemax-rangemin)
    dist1 = dist + abs(rangemax-i)
    dist2 = dist + abs(rangemax-(i-n))
    dist = len(lrs)
    dist += abs(rangemax)
    dist += abs(rangemax-rangemin)
    dist3 = dist + abs(rangemin-i)
    dist4 = dist + abs(rangemin-(i-n))
    #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
    ans = min(ans,dist1,dist2,dist3,dist4)

    #print(i,"finish")

print(ans)

Buggy submission (verdict: Runtime Error):
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#11:00

in1 = input()
in2 = input()
n = len(in1)
a,b = [],[]

for i in range(n):
    a.append(int(in1[i]))
    b.append(int(in2[i]))

if(sum(b)==0):
    if(sum(a)==0):
        print(0)
    else:
        print(-1)
    exit()

    
b3 = []
for i in range(3):
    for j in range(n):
        b3.append(b[j])

####

left = []
rightest = -1-n
for i in range(n):
    if(b[i]==1):
        rightest = i-n

for i in range(n):
    if(b[i]==1):
        rightest = i
    left.append(rightest-i)


right = []
leftest = 2*n
for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i +n

for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i
    right.append(leftest - (n-1-i))
right = [right[n-1-i] for i in range(n)]

#print(left,right)

ans = 10**18
for i in range(n):
    toFix = [0 for i in range(n)]
    lrs = []
    for j in range(n):
        ij = (i+j)%n
        if(a[j]!=b[ij]):
            toFix[j]=1
            lrs.append([left[j],right[j]])
    lrs.sort(key = lambda x : x[0])
    #print(lrs)
    leftmin = lrs[0][0]
    leftmax = lrs[-1][0]
    rightmin = n
    for j in lrs:
        rightmin = min(rightmin,j[1])
    
    rangemin = leftmin
    rangemax = leftmax
    for j in range(len(lrs)):
        dist = len(lrs)
        dist += abs(rangemin)
        dist += abs(rangemax-rangemin)
        dist1 = dist + abs(rangemax-i)
        dist2 = dist + abs(rangemax-(i-n))
        dist = len(lrs)
        dist += abs(rangemax)
        dist += abs(rangemax-rangemin)
        dist3 = dist + abs(rangemin-i)
        dist4 = dist + abs(rangemin-(i-n))
        #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
        ans = min(ans,dist1,dist2,dist3,dist4)

        rangemin = lrs[(j+1)%len(lrs)][0]
        rangemax = max(rangemax,lrs[j][1])
    rangemin = rightmin
    dist = len(lrs)
    dist += abs(rangemin)
    dist += abs(rangemax-rangemin)
    dist1 = dist + abs(rangemax-i)
    dist2 = dist + abs(rangemax-(i-n))
    dist = len(lrs)
    dist += abs(rangemax)
    dist += abs(rangemax-rangemin)
    dist3 = dist + abs(rangemin-i)
    dist4 = dist + abs(rangemin-(i-n))
    #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
    ans = min(ans,dist1,dist2,dist3,dist4)

    #print(i,"finish")

print(ans)

Buggy submission (verdict: Runtime Error):
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



#11:00

in1 = input()
in2 = input()
n = len(in1)
a,b = [],[]

for i in range(n):
    a.append(int(in1[i]))
    b.append(int(in2[i]))

if(sum(b)==0):
    if(sum(a)==0):
        print(0)
    else:
        print(-1)
    exit()

    
b3 = []
for i in range(3):
    for j in range(n):
        b3.append(b[j])

####

left = []
rightest = -1-n
for i in range(n):
    if(b[i]==1):
        rightest = i-n

for i in range(n):
    if(b[i]==1):
        rightest = i
    left.append(rightest-i)


right = []
leftest = 2*n
for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i +n

for i in range(n):
    if(b[n-1-i]==1):
        leftest = n-1-i
    right.append(leftest - (n-1-i))
right = [right[n-1-i] for i in range(n)]

#print(left,right)

ans = 10**18
for i in range(n):
    toFix = [0 for i in range(n)]
    lrs = []
    for j in range(n):
        ij = (i+j)%n
        if(a[j]!=b[ij]):
            toFix[j]==1
            lrs.append([left[j],right[j]])
    lrs.sort(key = lambda x : x[0])
    #print(lrs)
    leftmin = lrs[0][0]
    leftmax = lrs[-1][0]
    rightmin = n
    for j in lrs:
        rightmin = min(rightmin,j[1])
    
    rangemin = leftmin
    rangemax = leftmax
    for j in range(len(lrs)):
        dist = len(lrs)
        dist += abs(rangemin)
        dist += abs(rangemax-rangemin)
        dist1 = dist + abs(rangemax-i)
        dist2 = dist + abs(rangemax-(i-n))
        dist = len(lrs)
        dist += abs(rangemax)
        dist += abs(rangemax-rangemin)
        dist3 = dist + abs(rangemin-i)
        dist4 = dist + abs(rangemin-(i-n))
        #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
        ans = min(ans,dist1,dist2,dist3,dist4)

        rangemin = lrs[(j+1)%len(lrs)][0]
        rangemax = max(rangemax,lrs[j][1])
    rangemin = rightmin
    dist = len(lrs)
    dist += abs(rangemin)
    dist += abs(rangemax-rangemin)
    dist1 = dist + abs(rangemax-i)
    dist2 = dist + abs(rangemax-(i-n))
    dist = len(lrs)
    dist += abs(rangemax)
    dist += abs(rangemax-rangemin)
    dist3 = dist + abs(rangemin-i)
    dist4 = dist + abs(rangemin-(i-n))
    #print(dist1,dist2,dist3,dist4,rangemin,rangemax)
    ans = min(ans,dist1,dist2,dist3,dist4)

    #print(i,"finish")

print(ans)