Problem p02580 (python)

Fixed submission:
import sys, math, bisect



def solve(W_N, V_N, bombs, H, W):

    max_x = 1
    xs = []
    for i in range(W):
        if(W_N[i] > max_x):
            max_x = W_N[i]
            xs = [i]
        elif(W_N[i] == max_x):
            xs.append(i)
    max_y = 1
    ys = []
    for j in range(H):
        if(V_N[j] > max_y):
            max_y = V_N[j]
            ys = [j]
        elif(V_N[j] == max_y):
            ys.append(j)

    value = max_x + max_y

    for j in ys:

        bombs[j].sort()
        for i in xs:
            index = bisect.bisect_left(bombs[j], i)
            if(index == V_N[j] or i != bombs[j][index]):
                return value
            
    return value-1



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )


    V_N = [0] * H
    W_N = [0] * W
    bombs = [ [] for _ in range(H) ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )
        """
        W_N_bomb[x-1][0] += 1
        V_N_bomb[y-1][0] += 1
        """
        V_N[y-1] += 1
        W_N[x-1] += 1
        bombs[y-1].append(x-1)




    print( solve(W_N, V_N, bombs, H, W) )

Buggy submission (verdict: Runtime Error):
import sys, math, bisect



def solve(W_N, V_N, bombs, H, W):

    max_x = 1
    xs = []
    for i in range(W):
        if(W_N[i] > max_x):
            max_x = W_N[i]
            xs = [i]
        elif(W_N[i] == max_x):
            xs.append(i)
    max_y = 1
    ys = []
    for j in range(H):
        if(V_N[j] > max_y):
            max_y = V_N[j]
            ys = [j]
        elif(V_N[j] == max_y):
            ys.append(j)

    value = max_x + max_y

    for j in ys:

        bombs[j].sort()
        for i in xs:
            index = bisect.bisect_left(bombs[j], i)
            if( index < W and i != bombs[j][index] ):
            #if(  i != bombs[j][index] ):
                return value
    return value-1



if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )


    V_N = [0] * H
    W_N = [0] * W
    bombs = [ [] for _ in range(H) ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )
        """
        W_N_bomb[x-1][0] += 1
        V_N_bomb[y-1][0] += 1
        """
        V_N[y-1] += 1
        W_N[x-1] += 1
        bombs[y-1].append(x-1)




    print( solve(W_N, V_N, bombs, H, W) )

Buggy submission (verdict: Runtime Error):
import sys, math, heapq, bisect



def solve(W_N, V_N, bombs, H, W):

    max_x = 1
    xs = []
    for i in range(W):
        if(W_N[i] > max_x):
            max_x = W_N[i]
            xs = [i]
        elif(W_N[i] == max_x):
            xs.append(i)
    max_y = 1
    ys = []
    for j in range(H):
        if(V_N[j] > max_y):
            max_y = V_N[j]
            ys = [j]
        elif(V_N[j] == max_y):
            ys.append(j)

    value = max_x + max_y

    for j in ys:
        bombs[j].sort()
        for i in xs:
            index = bisect.bisect_left(bombs[j], i)
            if( i!=bombs[j][index] ):
                return value
    return value-1

    """
    for i in range( H ):
        if(V_N[i]==max_y):
            for j in range( W ):
                if(W_N[j]==max_x and W_N[j] not in bombs[i] ):
                #if(W_N[j]==max_x and bombs[i][j] == 0 ):

                    return value

    return value-1
    """

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )

    """
    V_N_bomb = [ [0, i]  for i in range(H) ]
    W_N_bomb = [ [0, i]  for i in range(W) ]
    """
    V_N = [0] * H
    W_N = [0] * W
    bombs = [ [] for _ in range(H) ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )
        """
        W_N_bomb[x-1][0] += 1
        V_N_bomb[y-1][0] += 1
        """
        V_N[y-1] += 1
        W_N[x-1] += 1
        bombs[y-1].append(x-1)


    """
    W_N_bomb.sort(key = lambda x: x[0])
    V_N_bomb.sort(key = lambda x: x[0])
    """

    print( solve(W_N, V_N, bombs, H, W) )

    """


    Ws = [ W_N_bomb[i][0] for i in range(W)]
    Hs = [ V_N_bomb[i][0] for i in range(H)]



    pos_x= bisect.bisect_left(Ws, Ws[-1])
    pos_y= bisect.bisect_left(Hs, Hs[-1])


    xs = W_N_bomb[pos_x:]
    ys = V_N_bomb[pos_y:]
    # xs.sort(key = lambda x: x[1])
    # ys.sort(key = lambda x: x[1])

    flag = False
    value = Ws[-1] + Hs[-1]

    for i in range( len(ys) ):
        for j in range( len(xs) ):
            if( bombs[i][j] == 1 ):
                flag = True
                break

    xs2 = [ xs[i][1] for i in range( len(xs) )]
    ys2 = [ ys[i][1] for i in range( len(ys) )]
    #print(W_N_bomb, V_N_bomb, pos_x, pos_y)
    flag = False
    value = Ws[-1] + Hs[-1]

    if(  bisect.bisect(bomb, xs[0]) != bisect.bisect(bomb, xs[-1]) ):
        flag = True
    else:
        for j in range(pos_y, H):
            pos_j = V_N_bomb[j][1]
            if(len(bombs[pos_j])==0 ):
                flag = True
                break
            indices = []
            for i in range(pos_x, W):
                pos_i = W_N_bomb[i][1]

                indices.append( bisect.bisect(bombs[pos_j], pos_i) )
                indices.sort()
                if(indices[0] != indices[-1])
                    flag=True
                    break

    if(flag==True):
        print(value)
    else:
        print(value-1)
    """

Buggy submission (verdict: Runtime Error):
import sys, math, heapq, bisect



def solve(W_N, V_N, bombs, H, W):

    max_x = 0
    xs = []
    for i in range(W):
        if(W_N[i] > max_x):
            max_x = W_N[i]
            xs = [i]
        elif(W_N[i] == max_x):
            xs.append(i)
    max_y = 0
    ys = []
    for j in range(H):
        if(W_N[j] > max_y):
            max_y = V_N[j]
            ys = [j]
        elif(V_N[j] == max_y):
            ys.append(j)

    value = max_x + max_y

    for i in xs:
        for j in ys:
            if(i not in bombs[j] ):
                return value
    return value-1

    """
    for i in range( H ):
        if(V_N[i]==max_y):
            for j in range( W ):
                if(W_N[j]==max_x and W_N[j] not in bombs[i] ):
                #if(W_N[j]==max_x and bombs[i][j] == 0 ):

                    return value

    return value-1
    """

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )

    """
    V_N_bomb = [ [0, i]  for i in range(H) ]
    W_N_bomb = [ [0, i]  for i in range(W) ]
    """
    V_N = [0] * H
    W_N = [0] * W
    bombs = [ [] for _ in range(H) ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )
        """
        W_N_bomb[x-1][0] += 1
        V_N_bomb[y-1][0] += 1
        """
        V_N[y-1] += 1
        W_N[x-1] += 1
        bombs[y-1].append(x-1)


    """
    W_N_bomb.sort(key = lambda x: x[0])
    V_N_bomb.sort(key = lambda x: x[0])
    """

    print( solve(W_N, V_N, bombs, H, W) )

    """


    Ws = [ W_N_bomb[i][0] for i in range(W)]
    Hs = [ V_N_bomb[i][0] for i in range(H)]



    pos_x= bisect.bisect_left(Ws, Ws[-1])
    pos_y= bisect.bisect_left(Hs, Hs[-1])


    xs = W_N_bomb[pos_x:]
    ys = V_N_bomb[pos_y:]
    # xs.sort(key = lambda x: x[1])
    # ys.sort(key = lambda x: x[1])

    flag = False
    value = Ws[-1] + Hs[-1]

    for i in range( len(ys) ):
        for j in range( len(xs) ):
            if( bombs[i][j] == 1 ):
                flag = True
                break

    xs2 = [ xs[i][1] for i in range( len(xs) )]
    ys2 = [ ys[i][1] for i in range( len(ys) )]
    #print(W_N_bomb, V_N_bomb, pos_x, pos_y)
    flag = False
    value = Ws[-1] + Hs[-1]

    if(  bisect.bisect(bomb, xs[0]) != bisect.bisect(bomb, xs[-1]) ):
        flag = True
    else:
        for j in range(pos_y, H):
            pos_j = V_N_bomb[j][1]
            if(len(bombs[pos_j])==0 ):
                flag = True
                break
            indices = []
            for i in range(pos_x, W):
                pos_i = W_N_bomb[i][1]

                indices.append( bisect.bisect(bombs[pos_j], pos_i) )
                indices.sort()
                if(indices[0] != indices[-1])
                    flag=True
                    break

    if(flag==True):
        print(value)
    else:
        print(value-1)
    """

Buggy submission (verdict: Runtime Error):
import sys, math, heapq, bisect



def solve(W_N, V_N, bombs):
    max_x = max(W_N)
    max_y = max(V_N)

    flag = False
    value = max_x + max_y

    for i in range( H ):
        if(V_N[i]==max_y):
            for j in range( W ):
                if(W_N[j]==max_x and bombs[i][j] == 0 ):
                    print(value)
                    return value

    return value-1

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )

    """
    V_N_bomb = [ [0, i]  for i in range(H) ]
    W_N_bomb = [ [0, i]  for i in range(W) ]
    """
    V_N = [0] * H
    W_N = [0] * W
    bombs = [  [0] * W for _ in range(H) ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )
        """
        W_N_bomb[x-1][0] += 1
        V_N_bomb[y-1][0] += 1
        """
        V_N[y-1] += 1
        W_N[x-1] += 1
        bombs[y-1][x-1] = 1


    """
    W_N_bomb.sort(key = lambda x: x[0])
    V_N_bomb.sort(key = lambda x: x[0])
    """

    print( solve(W_N, V_N, bombs) )

    """


    Ws = [ W_N_bomb[i][0] for i in range(W)]
    Hs = [ V_N_bomb[i][0] for i in range(H)]



    pos_x= bisect.bisect_left(Ws, Ws[-1])
    pos_y= bisect.bisect_left(Hs, Hs[-1])


    xs = W_N_bomb[pos_x:]
    ys = V_N_bomb[pos_y:]
    # xs.sort(key = lambda x: x[1])
    # ys.sort(key = lambda x: x[1])

    flag = False
    value = Ws[-1] + Hs[-1]

    for i in range( len(ys) ):
        for j in range( len(xs) ):
            if( bombs[i][j] == 1 ):
                flag = True
                break

    xs2 = [ xs[i][1] for i in range( len(xs) )]
    ys2 = [ ys[i][1] for i in range( len(ys) )]
    #print(W_N_bomb, V_N_bomb, pos_x, pos_y)
    flag = False
    value = Ws[-1] + Hs[-1]

    if(  bisect.bisect(bomb, xs[0]) != bisect.bisect(bomb, xs[-1]) ):
        flag = True
    else:
        for j in range(pos_y, H):
            pos_j = V_N_bomb[j][1]
            if(len(bombs[pos_j])==0 ):
                flag = True
                break
            indices = []
            for i in range(pos_x, W):
                pos_i = W_N_bomb[i][1]

                indices.append( bisect.bisect(bombs[pos_j], pos_i) )
                indices.sort()
                if(indices[0] != indices[-1])
                    flag=True
                    break

    if(flag==True):
        print(value)
    else:
        print(value-1)
    """

Buggy submission (verdict: Runtime Error):
import sys, math, heapq, bisect





if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )

    """
    V_N_bomb = [ [0, i]  for i in range(H) ]
    W_N_bomb = [ [0, i]  for i in range(W) ]
    """
    V_N = [0] * H
    W_N = [0] * W
    bombs = [  [0] * W for _ in range(H) ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )
        """
        W_N_bomb[x-1][0] += 1
        V_N_bomb[y-1][0] += 1
        """
        V_N[y-1] += 1
        W_N[x-1] += 1
        bombs[y-1][x-1] = 1


    """
    W_N_bomb.sort(key = lambda x: x[0])
    V_N_bomb.sort(key = lambda x: x[0])
    """


    max_x = max(W_N)
    max_y = max(V_N)

    flag = False
    value = max_x + max_y

    for i in range( H ):
        if(V_N[i]==max_y):
            for j in range( W ):
                if(W_N[j]==max_x and bombs[i][j] == 0 ):
                    print(value)
                    sys.exit()

    print(value-1)
    """


    Ws = [ W_N_bomb[i][0] for i in range(W)]
    Hs = [ V_N_bomb[i][0] for i in range(H)]



    pos_x= bisect.bisect_left(Ws, Ws[-1])
    pos_y= bisect.bisect_left(Hs, Hs[-1])


    xs = W_N_bomb[pos_x:]
    ys = V_N_bomb[pos_y:]
    # xs.sort(key = lambda x: x[1])
    # ys.sort(key = lambda x: x[1])

    flag = False
    value = Ws[-1] + Hs[-1]

    for i in range( len(ys) ):
        for j in range( len(xs) ):
            if( bombs[i][j] == 1 ):
                flag = True
                break

    xs2 = [ xs[i][1] for i in range( len(xs) )]
    ys2 = [ ys[i][1] for i in range( len(ys) )]
    #print(W_N_bomb, V_N_bomb, pos_x, pos_y)
    flag = False
    value = Ws[-1] + Hs[-1]

    if(  bisect.bisect(bomb, xs[0]) != bisect.bisect(bomb, xs[-1]) ):
        flag = True
    else:
        for j in range(pos_y, H):
            pos_j = V_N_bomb[j][1]
            if(len(bombs[pos_j])==0 ):
                flag = True
                break
            indices = []
            for i in range(pos_x, W):
                pos_i = W_N_bomb[i][1]

                indices.append( bisect.bisect(bombs[pos_j], pos_i) )
                indices.sort()
                if(indices[0] != indices[-1])
                    flag=True
                    break

    if(flag==True):
        print(value)
    else:
        print(value-1)
    """

Buggy submission (verdict: Runtime Error):
import sys, math, heapq, bisect





if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )

    H_N_bomb = [ [0, i]  for i in range(H) ]
    W_N_bomb = [ [0, i]  for i in range(W) ]
    bombs = [  [0] * W for _ in range(H) ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )

        W_N_bomb[x-1][0] += 1
        H_N_bomb[y-1][0] += 1
        bombs[y-1][x-1] = 1



    W_N_bomb.sort(key = lambda x: x[0])
    H_N_bomb.sort(key = lambda x: x[0])



    Ws = [ W_N_bomb[i][0] for i in range(W)]
    Hs = [ H_N_bomb[i][0] for i in range(H)]



    pos_x= bisect.bisect_left(Ws, Ws[-1])
    pos_y= bisect.bisect_left(Hs, Hs[-1])


    xs = W_N_bomb[pos_x:]
    ys = H_N_bomb[pos_y:]
    # xs.sort(key = lambda x: x[1])
    # ys.sort(key = lambda x: x[1])
    flag = False
    value = Ws[-1] + Hs[-1]

    for i in range( len(ys) ):
        for j in range( len(xs) ):
            if( bombs[i][j] == 1 ):
                flag = True
                break
    """

    xs2 = [ xs[i][1] for i in range( len(xs) )]
    ys2 = [ ys[i][1] for i in range( len(ys) )]
    #print(W_N_bomb, H_N_bomb, pos_x, pos_y)
    flag = False
    value = Ws[-1] + Hs[-1]

    if(  bisect.bisect(bomb, xs[0]) != bisect.bisect(bomb, xs[-1]) ):
        flag = True
    else:
        for j in range(pos_y, H):
            pos_j = H_N_bomb[j][1]
            if(len(bombs[pos_j])==0 ):
                flag = True
                break
            indices = []
            for i in range(pos_x, W):
                pos_i = W_N_bomb[i][1]

                indices.append( bisect.bisect(bombs[pos_j], pos_i) )
                indices.sort()
                if(indices[0] != indices[-1])
                    flag=True
                    break
    """
    if(flag==True):
        print(value)
    else:
        print(value-1)

Buggy submission (verdict: Runtime Error):
import sys, math, heapq, bisect





if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )

    H_N_bomb = [ [0, i]  for i in range(H) ]
    W_N_bomb = [ [0, i]  for i in range(W) ]
    bombs = [ [0]*W for _ in range(H)  ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )

        W_N_bomb[x-1][0] += 1
        H_N_bomb[y-1][0] += 1
        bombs[y-1][x-1] = 1


    W_N_bomb.sort(key = lambda x: x[0])
    H_N_bomb.sort(key = lambda x: x[0])



    Ws = [0] * W
    Hs = [0] * H
    for i in range(W):
        Ws[i] = W_N_bomb[i][0]
    for i in range(H):
        Hs[i] = H_N_bomb[i][0]

    pos_x= bisect.bisect_left(Ws, Ws[-1])
    pos_y= bisect.bisect_left(Hs, Hs[-1])
    #print(W_N_bomb, H_N_bomb, pos_x, pos_y)
    flag = False
    value = Ws[-1] + Hs[-1]
    for i in range(pos_x, W):
        for j in range(pos_y, H):
            pos_i = W_N_bomb[i][1]
            pos_j = H_N_bomb[j][1]
            if(bombs[pos_j][pos_i]==0):
                flag=True
                break
    if(flag==True):
        print(value)
    else:
        print(value-1)

Buggy submission (verdict: Runtime Error):
import sys, math, heapq, bisect





if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )

    H_N_bomb = [ [0, i]  for i in range(H) ]
    W_N_bomb = [ [0, i]  for i in range(W) ]
    bombs = [ [0]*W for _ in range(H)  ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )

        W_N_bomb[x-1][0] += 1
        H_N_bomb[y-1][0] += 1
        bombs[y-1][x-1] = 1


    W_N_bomb.sort(key = lambda x: x[0])
    H_N_bomb.sort(key = lambda x: x[0])



    Ws = [0] * W
    Hs = [0] * H
    for i in range(W):
        Ws[i] = W_N_bomb[i][0]
    for i in range(H):
        Hs[i] = H_N_bomb[i][0]

    pos_x= bisect.bisect_left(Ws, Ws[-1])
    pos_y= bisect.bisect_left(Hs, Hs[-1])
    #print(W_N_bomb, H_N_bomb, pos_x, pos_y)
    flag = False
    value = Ws[i] + Hs[j]
    for i in range(pos_x, W):
        for j in range(pos_y, H):
            pos_i = W_N_bomb[i][1]
            pos_j = H_N_bomb[j][1]
            if(bombs[pos_j][pos_i]==0):
                flag=True
                break
    if(flag==True):
        print(value)
    else:
        print(value-1)

Buggy submission (verdict: Runtime Error):
import sys, math, heapq, bisect





if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W, N_bombs= map(int, input().strip().split() )

    H_N_bomb = [ [0, i]  for i in range(H) ]
    W_N_bomb = [ [0, i]  for i in range(W) ]
    bombs = [ [0]*W for _ in range(H)  ]


    for i in range(N_bombs):
        y, x = map(int, input().strip().split() )

        W_N_bomb[x-1][0] += 1
        H_N_bomb[y-1][0] += 1
        bombs[y-1][x-1] = 1


    W_N_bomb.sort(key = lambda x: x[0])
    H_N_bomb.sort(key = lambda x: x[0])
    queues = []


    Ws = [0] * W
    Hs = [0] * H
    for i in range(W):
        Ws[i] = W_N_bomb[i][0]
    for i in range(H):
        Hs[i] = H_N_bomb[i][0]

    pos_x= bisect.bisect_left(Ws, Ws[-1])
    pos_y= bisect.bisect_left(Hs, Hs[-1])
    #print(W_N_bomb, H_N_bomb, pos_x, pos_y)
    for i in range(pos_x, W):
        for j in range(pos_y, H):
            value = Ws[i] + Hs[j]
            pos_i = W_N_bomb[i][1]
            pos_j = H_N_bomb[j][1]
            if(bombs[pos_j][pos_i]==1):
                value -= 1
            heapq.heappush(queues, (-1) * value)
    print(-1 * queues[0])