Problem p02704 (python)

Fixed submission:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
#import pysnooper # @pysnooper.snoop() #TODO

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class Solver:

    def __init__(self, n, s_list, t_list, u_list, v_list):
        self.n = n
        self.s_list = s_list
        self.t_list = t_list
        self.u_list = u_list
        self.v_list = v_list
        self.size = 64
        #self.size = 1 # debug
        self.bit_key = 1
        self.mode = 'l' # l or c
        self.ans = self.make_ans()

    def make_ans(self):
        ans = [None] * self.n
        for l in range(self.n):
            ans[l] = [0] * self.n
        return ans

    def print_ans(self):
        for l in range(self.n):
            for c in range(self.n):
                print(self.ans[l][c], end=" ")
            print("")


    def add_straight(self, key, value):
        if not value:
            return
        if self.mode == 'l':
            for c in range(self.n):
                self.ans[key][c] |= self.bit_key
        else:
            for l in range(self.n):
                self.ans[l][key] |= self.bit_key

    def add(self, key, sub_key, value):
        if not value:
            return
        if self.mode == 'l':
            l, c = key, sub_key
        else:
            l, c = sub_key, key
        self.ans[l][c] |= self.bit_key

    def run(self):
        try:
            for bit in range(self.size):
                self.bit_key = 1 << bit
                self.solve_for_bit()
        except RuntimeError as err:
            #raise err # debug
            return False
        return True

    def solve_for_bit(self):
        # determine
        self.mode = 'l'
        filled_l, ambiguous_l = self.determine(self.s_list, self.u_list)
        #print('filled_l, ambiguous_l') # debug
        #print(filled_l, ambiguous_l) # debug
        self.mode = 'c'
        filled_c, ambiguous_c = self.determine(self.t_list, self.v_list)
        #print('filled_c, ambiguous_c') # debug
        #print(filled_c, ambiguous_c) # debug
        #print('self.ans') # debug
        #self.print_ans() # debug
        # check
        if filled_l[0] and filled_c[1] or filled_l[1] and filled_c[0]:
            #print('hoge') # debug
            raise RuntimeError
        # fill 1 straight or like checker
        if len(ambiguous_l) == 1:
            self.handle_straight('l', filled_l, ambiguous_l, filled_c, ambiguous_c)
        elif len(ambiguous_c) == 1:
            self.handle_straight('c', filled_c, ambiguous_c, filled_l, ambiguous_l)
        else:
            self.checker_fill(ambiguous_l, ambiguous_c)

    def determine(self, l1, l2):
        filled = [False, False]
        ambiguous = [] # (key, wanted)
        for key in range(self.n):
            st = l1[key]
            uv = 1 if l2[key] & self.bit_key else 0
            if st == uv:
                ambiguous.append((key, uv))
                continue
            filled[uv] = True
            self.add_straight(key, uv)
        return filled, ambiguous

    def handle_straight(self, mode, filled, ambiguous, sub_filled, sub_ambiguous):
        #print('self.ans') # debug
        #print(self.ans) # debug
        self.mode = mode
        key, wanted = ambiguous[0]
        ok = False
        if sub_filled[wanted]:
            ok = True
        for sub_key, sub_wanted in sub_ambiguous:
            if filled[sub_wanted]:
                # sub_wanted is satisfied, so use for wanted
                self.add(key, sub_key, wanted)
                ok = True
            else:
                # satisfy sub_wanted
                self.add(key, sub_key, sub_wanted)
                if wanted == sub_wanted:
                    ok = True
        if not ok:
            raise RuntimeError

    def checker_fill(self, ambiguous_l, ambiguous_c):
        self.mode = 'l'
        for il, (l_key, _) in enumerate(ambiguous_l):
            for ic, (c_key, _) in enumerate(ambiguous_c):
                v = (il + ic) % 2 == 0
                #print('l_key, c_key', l_key, c_key) # debug
                self.add(l_key, c_key, v)


if __name__ == '__main__':
    n = int(input())
    s_list = list(map(int, input().split()))
    t_list = list(map(int, input().split()))
    u_list = list(map(int, input().split()))
    v_list = list(map(int, input().split()))
    #print('n, s_list, t_list, u_list, v_list') # debug
    #print(n, s_list, t_list, u_list, v_list) # debug
    solver = Solver(n, s_list, t_list, u_list, v_list)
    ans = solver.run()
    if ans is False:
        print(-1)
    else:
        solver.print_ans()

    #print('\33[32m' + 'end' + '\033[0m') # debug

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
#import pysnooper # @pysnooper.snoop() #TODO

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class Solver:

    def __init__(self, n, s_list, t_list, u_list, v_list):
        self.n = n
        self.s_list = s_list
        self.t_list = t_list
        self.u_list = u_list
        self.v_list = v_list
        self.size = 64
        self.bit_key = 1
        self.mode = 'l' # l or c
        self.ans = self.make_ans()

    def make_ans(self):
        ans = [None] * self.n
        for l in range(self.n):
            ans[l] = [0] * self.n
        return ans

    def print_ans(self):
        for l in range(self.n):
            for c in range(self.n):
                print(self.ans[l][c], end=" ")
            print("")


    def add_straight(self, key, value):
        if not value:
            return
        if self.mode == 'l':
            for c in range(self.n):
                self.ans[key][c] |= self.bit_key
        else:
            for l in range(self.n):
                self.ans[l][key] |= self.bit_key

    def add(self, key, sub_key, value):
        if not value:
            return
        if self.mode == 'l':
            l, c = key, sub_key
        else:
            l, c = sub_key, key
        self.ans[l][c] |= self.bit_key

    def run(self):
        try:
            for bit in range(self.size):
                self.bit_key = 1 << bit
                self.solve_for_bit()
        except RuntimeError as err:
            raise err
            return False
        return True

    def solve_for_bit(self):
        # determine
        self.mode = 'l'
        filled_l, ambiguous_l = self.determine(self.s_list, self.u_list)
        self.mode = 'c'
        filled_c, ambiguous_c = self.determine(self.t_list, self.v_list)
        #print('self.ans') # debug
        #print(self.ans) # debug
        # check
        if filled_l[0] and filled_c[1] or filled_l[1] and filled_l[0]:
            raise RuntimeError
        # fill 1 straight or like checker
        if len(ambiguous_l) == 1:
            self.handle_straight('l', filled_l, ambiguous_l, filled_c, ambiguous_c)
        elif len(ambiguous_c) == 1:
            self.handle_straight('c', filled_c, ambiguous_c, filled_l, ambiguous_l)
        else:
            self.checker_fill(ambiguous_l, ambiguous_c)

    def determine(self, l1, l2):
        filled = [False, False]
        ambiguous = [] # (key, wanted)
        for key in range(self.n):
            st = l1[key]
            uv = 1 if l2[key] & self.bit_key else 0
            #print('uv') # debug
            #print(uv) # debug
            if st == uv:
                ambiguous.append((key, uv))
                continue
            filled[uv] = True
            self.add_straight(key, uv)
        return filled, ambiguous

    def handle_straight(self, mode, filled, ambiguous, sub_filled, sub_ambiguous):
        #print('self.ans') # debug
        #print(self.ans) # debug
        self.mode = mode
        key, wanted = ambiguous[0]
        ok = False
        if sub_filled[wanted]:
            ok = True
        for sub_key, sub_wanted in sub_ambiguous:
            if filled[sub_wanted]:
                # sub_wanted is satisfied, so use for wanted
                self.add(key, sub_key, wanted)
                ok = True
            else:
                # satisfy sub_wanted
                self.add(key, sub_key, sub_wanted)
                if wanted == sub_wanted:
                    ok = True
        if not ok:
            raise RuntimeError

    def checker_fill(self, ambiguous_l, ambiguous_c):
        self.mode = 'l'
        for il, (l_key, _) in enumerate(ambiguous_l):
            for ic, (c_key, _) in enumerate(ambiguous_l):
                v = (il + ic) % 2 == 0
                self.add(l_key, c_key, v)


if __name__ == '__main__':
    n = int(input())
    s_list = list(map(int, input().split()))
    t_list = list(map(int, input().split()))
    u_list = list(map(int, input().split()))
    v_list = list(map(int, input().split()))
    solver = Solver(n, s_list, t_list, u_list, v_list)
    ans = solver.run()
    if ans is False:
        print(-1)
    else:
        solver.print_ans()

    #print('\33[32m' + 'end' + '\033[0m') # debug

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

size = 4

class Solver():

    def __init__(self, n, s_list, t_list, u_list, v_list, size):
        self.n = n
        self.s_list = s_list
        self.t_list = t_list
        self.u_list = u_list # var[bit_key][l] = bool
        self.v_list = v_list # var[bit_key][c] = bool
        self.size = size
        self.a = None
        self.d = None
        self.ans = self.make_ans_array(n)

    @staticmethod
    def make_ad_array(n):
        new = [None] * n
        for i in range(n):
            new[i] = [False] * n
        return new

    @staticmethod
    def make_ans_array(n):
        new = [None] * n
        for i in range(n):
            new[i] = [""] * n
        return new

    def save_a(self):
        for l in range(self.n):
            for c in range(self.n):
                char = '1' if self.a[l][c] else '0'
                self.ans[l][c] += char

    def print_arr(self, arr):
        for l in range(self.n):
            for c in range(self.n):
                v = 1 if arr[l][c] else 0
                print(v, end=" ")
            print("")

    def print_ans(self):
        for l in range(self.n):
            for c in range(self.n):
                v = int(self.ans[l][c], 2)
                print(v, end=" ")
            print("")

    def run(self):
        try:
            for bit_key in range(self.size):
                self.a = self.make_ad_array(n)
                self.d = self.make_ad_array(n)
                #print('self.u_list[bit_key]') # debug
                #print(self.u_list[bit_key]) # debug
                #print('self.v_list[bit_key]') # debug
                #print(self.v_list[bit_key]) # debug
                self.step_determine(bit_key)
                #print('self.a') # debug
                #self.print_arr(self.a) # debug
                #print('self.d') # debug
                #self.print_arr(self.d) # debug
                self.step_check_and_fill(bit_key)
                #print('self.a') # debug
                #self.print_arr(self.a) # debug
                #print('self.d') # debug
                #self.print_arr(self.d) # debug
                self.step_checker(bit_key)
                #print('self.a') # debug
                #self.print_arr(self.a) # debug
                #print('self.d') # debug
                #self.print_arr(self.d) # debug
                self.save_a()
                #print('self.ans') # debug
                #self.print_ans() # debug
        except RuntimeError as err:
            #raise err # debug
            return False

    def mode_lc(self, key, sub_key):
        if self.mode == 'l':
            l = key
            c = sub_key
        else:
            l = sub_key
            c = key
        return l, c

    def set(self, key, value):
        for i in range(self.n):
            l, c = self.mode_lc(key, i)
            if self.d[l][c] and self.a[l][c] != value:
                raise RuntimeError
            self.a[l][i] = value
            self.d[l][i] = True

    def set_one(self, key, pos, value):
        l, c = self.mode_lc(key, pos)
        self.a[l][c] = value
        self.d[l][c] = True

    def check_at_least_one(self, key, wanted):
        """
        return not yet determined pos, if found just 1 such pos
        """
        ok = False
        not_yet = []
        for pos in range(self.n):
            l, c = self.mode_lc(key, pos)
            if not self.d[l][c]:
                not_yet.append(pos)
            if self.a[l][c] == wanted:
                ok = True
        if not ok and len(not_yet) == 0:
            raise RuntimeError
        if len(not_yet) == 1:
            return not_yet[0]
        else:
            return None

    def get_not_yet(self):
        not_yet_l = []
        for l in range(self.n):
            for c in range(self.n):
                if self.d[l][c] == False:
                    not_yet_l.append(l)
                    break

        not_yet_c = []
        for c in range(self.n):
            for l in range(self.n):
                if self.d[l][c] == False:
                    not_yet_c.append(c)
                    break
        return not_yet_l, not_yet_c



    def step_determine(self, bit_key):
        self.mode = 'l'
        self.determine(self.s_list, self.u_list[bit_key])
        self.mode = 'c'
        self.determine(self.t_list, self.v_list[bit_key])

    def determine(self, l1, l2):
        for key in range(self.n):
            if l1[key] == l2[key]:
                continue
            self.set(key, l2[key])

    def step_check_and_fill(self, bit_key):
        for _ in range(2):
            self.mode = 'l'
            self.check_and_fill(self.s_list, self.u_list[bit_key])
            self.mode = 'c'
            self.check_and_fill(self.t_list, self.v_list[bit_key])

    def check_and_fill(self, l1, l2):
        for key in range(self.n):
            if l1[key] != l2[key]:
                continue
            wanted = l2[key]
            not_yet_pos = self.check_at_least_one(key, wanted)
            if not_yet_pos is not None:
                self.set_one(key, not_yet_pos, wanted)

    def step_checker(self, bit_key):
        not_yet_l, not_yet_c = self.get_not_yet()
        for il, l in enumerate(not_yet_l):
            for ic, c in enumerate(not_yet_c):
                v = (il + ic) % 2 == 0
                self.set_one(l, c, v)
















def int_to_01(val):
    f = "{:0=" + str(size) + "b}"
    binary_str = f.format(val)
    return binary_str

def arrange_uv_list(n, l):
    new = [None] * size
    for bit_key in range(size):
        new[bit_key] = [None] * n
    for key, v in enumerate(l):
        s = int_to_01(v)
        for bit_key, bs in enumerate(s):
            if bs == "0":
                new[bit_key][key] = False
            else:
                new[bit_key][key] = True
    return new


if __name__ == '__main__':
    n = int(input())
    s_list = list(map(int, input().split()))
    t_list = list(map(int, input().split()))
    u_list = list(map(int, input().split()))
    v_list = list(map(int, input().split()))
    u_list = arrange_uv_list(n, u_list)
    v_list = arrange_uv_list(n, v_list)
    solver = Solver(n, s_list, t_list, u_list, v_list, size)
    res = solver.run()
    if res == False:
        print(-1)
    else:
        solver.print_ans()


    #print('\33[32m' + 'end' + '\033[0m') # debug

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
#from bitarray import bitarray # no in atcoder
import bisect
import numpy as np
from ctypes import c_ulonglong as ull

a = None # answer array
d = None # determined or not
size = 64

class Bitarray(list):

    def __init__(self, size, data=None):
        self.size = size
        if data is None:
            self.data = [False] * size
        else:
            self.data = data[:]

    @staticmethod
    def true(size):
        new = Bitarray(size)
        new.data = [True] * size
        return new

    @staticmethod
    def false(size):
        new = Bitarray(size)
        new.data = [False] * size
        return new

    @staticmethod
    def from_int(size, val):
        new = Bitarray(size)
        f = "{:0=" + str(size) + "b}"
        binary_str = f.format(val)
        for i, b in enumerate(binary_str):
            if b == '1':
                new.data[i] = True
            else:
                new.data[i] = False
        return new

    def bitwise(self, other, op):
        assert(self.size == other.size)
        for i in range(self.size):
           self.data[i] = op(self.data[i], other.data[i])

    @staticmethod
    def op_and(a, b):
        return a and b

    @staticmethod
    def op_or(a, b):
        return a or b

    def __repr__(self):
        out = ""
        for d in self.data:
            c = "1" if d else "0"
            out += c
        return out

    def to_int(self):
        return int(self.__repr__(), 2)

    def __getitem__(self, key):
        return self.data[key]

    def __setitem__(self, key, value):
        self.data[key] = value

    def __iter__(self):
        return self.data.__iter__()

    def __and__(self, other): # &
        new = Bitarray(self.size, self.data)
        new.bitwise(other, Bitarray.op_and)
        return new

    def __iadd__(self, other):
        self.bitwise(other, Bitarray.op_and)
        return self

    def __or__(self, other): # |
        new = Bitarray(self.size, self.data)
        new.bitwise(other, Bitarray.op_or)
        return new

    def __ior__(self, other):
        self.bitwise(other, Bitarray.op_or)
        return self

    def __invert__(self): # ~
        new = Bitarray(self.size)
        for i in range(new.size):
            new.data[i] = not self.data[i]
        return new

def make_a(n):
    global a
    global d
    a = [None] * n
    d = [None] * n
    for i in range(n):
        a[i] = [None] * n
        d[i] = [None] * n
        for j in range(n):
            a[i][j] = Bitarray(size)
            d[i][j] = Bitarray(size)


def t2t(l, c, bit): # True to True, 1 to 1
    #TODO check impossible
    global a
    global d
    a[l][c] |= bit
    d[l][c] |= bit

def f2f(l, c, bit): # False to False, 0 to 0
    #TODO check impossible
    global a
    global d
    a[l][c] &= bit
    d[l][c] |= ~bit

def print_arr(arr):
    n = len(arr)
    for l in range(n):
        for c in range(n):
            v = arr[l][c].to_int()
            #v = arr[l][c] # debug
            print(v, end=" ")
        print("")

def to_bitarray_list(l):
    for i, v in enumerate(l):
        l[i] = Bitarray.from_int(size, v)
    return l

def determine(n, s_list, t_list, u_list, v_list):
    global a
    global d
    # for s, u
    for l in range(n):
        u = u_list[l]
        if s_list[l] == 0:
            for i in range(n):
                t2t(l, i, u)
        else:
            for i in range(n):
                f2f(l, i, u)
    # for t, v
    for c in range(n):
        v = v_list[c]
        if t_list[c] == 0:
            for i in range(n):
                t2t(i, c, v)
        else:
            for i in range(n):
                f2f(i, c, v)

def check_and_fill(n, s_list, t_list, u_list, v_list, bit_key):
    global a
    global d
    for _ in range(2):
        # for s, u
        for l in range(n):
            not_yet = []
            want = u_list[l][bit_key]
            ok = False
            for c in range(n):
                if d[l][c][bit_key] == False:
                    not_yet.append(c)
                    continue
                if a[l][c][bit_key] == want:
                    ok = True
            #print('s u not_yet') # debug
            #print(not_yet) # debug
            if ok:
                continue
            if len(not_yet) == 0:
                return False
            if len(not_yet) == 1:
                c = not_yet[0]
                a[l][c][bit_key] = want
                d[l][c][bit_key] = True
        # for t, v
        for c in range(n):
            not_yet = []
            want = v_list[c][bit_key]
            ok = False
            for l in range(n):
                if d[l][c][bit_key] == False:
                    not_yet.append(c)
                    continue
                if a[l][c][bit_key] == want:
                    ok = True
            #print('t v not_yet ok, want') # debug
            #print(not_yet, ok, want) # debug
            if ok:
                continue
            if len(not_yet) == 0:
                return False
            if len(not_yet) == 1:
                l = not_yet[0]
                a[l][c][bit_key] = want
                d[l][c][bit_key] = True
    return True

def checker(n, s_list, t_list, u_list, v_list, bit_key):
    # for s, u
    not_yet_l = []
    for l in range(n):
        for c in range(n):
            #print('l, c, d[l][c][bit_key] ') # debug
            #print(l, c, d[l][c][bit_key] ) # debug
            if d[l][c][bit_key] == False:
                not_yet_l.append(l)
                break
    # for t, v
    not_yet_c = []
    for c in range(n):
        for l in range(n):
            if d[l][c][bit_key] == False:
                not_yet_c.append(c)
                break
    for il, l in enumerate(not_yet_l):
        for ic, c in enumerate(not_yet_c):
            b = (il + ic) % 2 == 0
            a[l][c][bit_key] = b


def solve(n, s_list, t_list, u_list, v_list):
    determine(n, s_list, t_list, u_list, v_list)
    for bit_key in range(size):
        successed = check_and_fill(n, s_list, t_list, u_list, v_list, bit_key)
        if not successed:
            #print('not successed') # debug TODO unexpected not successed
            return False
        checker(n, s_list, t_list, u_list, v_list, bit_key)





if __name__ == '__main__':
    n = int(input())
    s_list = list(map(int, input().split()))
    t_list = list(map(int, input().split()))
    u_list = list(map(int, input().split()))
    v_list = list(map(int, input().split()))
    u_list = to_bitarray_list(u_list)
    v_list = to_bitarray_list(v_list)
    #print('u_list') # debug
    #print(u_list) # debug
    #print('type(u_list[0])') # debug
    #print(type(u_list[0])) # debug
    make_a(n)

    solve(n, s_list, t_list, u_list, v_list)


    #print('a') # debug
    print_arr(a)
    #print('d') # debug
    #print_arr(d) # debug



    #print('\33[32m' + 'end' + '\033[0m') # debug