Problem p02942 (python)

Fixed submission:
import sys
readline = sys.stdin.readline

import collections
class Dinic:
    def __init__(self, vnum):
        self.edge = [[] for i in range(vnum)]
        self.n = vnum
        # infはint型の方が良いかもね
        self.inf = float('inf')
    def addedge(self, st, en, c):
        self.edge[st].append([en, c, len(self.edge[en])])
        self.edge[en].append([st, 0, len(self.edge[st])-1])
    def bfs(self, vst):
        dist = [-1]*self.n
        dist[vst] = 0
        Q = collections.deque([vst])
        while Q:
            nv = Q.popleft()
            for vt, c, r in self.edge[nv]:
                if dist[vt] == -1 and c > 0:
                    dist[vt] = dist[nv] + 1
                    Q.append(vt)
        self.dist = dist
    def dfs(self, nv, en, nf):
        nextv = self.nextv
        if nv == en:
            return nf
        dist = self.dist
        ist = nextv[nv]
        for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
            if dist[nv] < dist[vt] and c > 0:
                df = self.dfs(vt, en, min(nf, c))
                if df > 0:
                    self.edge[nv][i][1] -= df
                    self.edge[vt][r][1] += df
                    return df
            nextv[nv] += 1
        return 0
    def getmf(self, st, en):
        mf = 0
        while True:
            self.bfs(st)
            if self.dist[en] == -1:
                break
            self.nextv = [0]*self.n
            while True:
                fl = self.dfs(st, en, self.inf)
                if fl > 0:
                    mf += fl
                else:
                    break
        return mf



N, M = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(N)]


B = [[None]*M for _ in range(N)]

st = 2*N
en = 2*N+1
used = set()
for num in range(M):
    T = Dinic(2*N+2)
    for i in range(N):
        T.addedge(st, i, 1)
        T.addedge(N+i, en, 1)
        for j in range(M):
            aij = A[i][j]
            if aij not in used:
                T.addedge(i, N+(aij-1)//M, 1)
    
    T.getmf(st, en)
    for i in range(N):
        candi = [e for e, cost, _ in T.edge[i+N] if cost == 1][0]
        for j in range(M):
            if A[candi][j] not in used and (A[candi][j]-1)//M == i:
                used.add(A[candi][j])
                B[candi][num] = A[candi][j]
                break
C = list(map(list, zip(*B)))
C = [sorted(c) for c in C]
C = list(map(list, zip(*C)))

for b in B:
    print(*b)

for c in C:
    print(*c)

Buggy submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline

import collections
class Dinic:
    def __init__(self, vnum):
        self.edge = [[] for i in range(vnum)]
        self.n = vnum
        # infはint型の方が良いかもね
        self.inf = float('inf')
    def addedge(self, st, en, c):
        self.edge[st].append([en, c, len(self.edge[en])])
        self.edge[en].append([st, 0, len(self.edge[st])-1])
    def bfs(self, vst):
        dist = [-1]*self.n
        dist[vst] = 0
        Q = collections.deque([vst])
        while Q:
            nv = Q.popleft()
            for vt, c, r in self.edge[nv]:
                if dist[vt] == -1 and c > 0:
                    dist[vt] = dist[nv] + 1
                    Q.append(vt)
        self.dist = dist
    def dfs(self, nv, en, nf):
        nextv = self.nextv
        if nv == en:
            return nf
        dist = self.dist
        ist = nextv[nv]
        for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
            if dist[nv] < dist[vt] and c > 0:
                df = self.dfs(vt, en, min(nf, c))
                if df > 0:
                    self.edge[nv][i][1] -= df
                    self.edge[vt][r][1] += df
                    return df
            nextv[nv] += 1
        return 0
    def getmf(self, st, en):
        mf = 0
        while True:
            self.bfs(st)
            if self.dist[en] == -1:
                break
            self.nextv = [0]*self.n
            while True:
                fl = self.dfs(st, en, self.inf)
                if fl > 0:
                    mf += fl
                else:
                    break
        return mf



N, M = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(N)]

num = [[] for _ in range(N)]

for i in range(N):
    for j in range(M):
        num[(A[i][j]-1)//M].append((i, j))

B = [[None]*M for _ in range(N)]

st = 2*M
en = 2*M+1
for ni in range(N):
    T = Dinic(2*M+2)
    for idx in range(M):
        T.addedge(st, idx, 1)
        T.addedge(M+idx, en, 1)
        ai, aj = num[ni][idx]
        for ji in range(M):
            if B[ai][ji] is None:
                T.addedge(idx, M+ji, 1)
    
    T.getmf(st, en)
    for j in range(M):
        candi = [e for e, cost, _ in T.edge[j+M] if cost == 1][0]
        ai, aj = num[ni][candi]
        B[ai][j] = A[ai][aj]
    
C = list(map(list, zip(*B)))
C = [sorted(c) for c in C]
C = list(map(list, zip(*C)))

for b in B:
    print(*b)

for c in C:
    print(*c)

Buggy submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline

import collections
class Dinic:
    def __init__(self, vnum):
        self.edge = [[] for i in range(vnum)]
        self.n = vnum
        # infはint型の方が良いかもね
        self.inf = float('inf')
    def addedge(self, st, en, c):
        self.edge[st].append([en, c, len(self.edge[en])])
        self.edge[en].append([st, 0, len(self.edge[st])-1])
    def bfs(self, vst):
        dist = [-1]*self.n
        dist[vst] = 0
        Q = collections.deque([vst])
        while Q:
            nv = Q.popleft()
            for vt, c, r in self.edge[nv]:
                if dist[vt] == -1 and c > 0:
                    dist[vt] = dist[nv] + 1
                    Q.append(vt)
        self.dist = dist
    def dfs(self, nv, en, nf):
        nextv = self.nextv
        if nv == en:
            return nf
        dist = self.dist
        ist = nextv[nv]
        for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
            if dist[nv] < dist[vt] and c > 0:
                df = self.dfs(vt, en, min(nf, c))
                if df > 0:
                    self.edge[nv][i][1] -= df
                    self.edge[vt][r][1] += df
                    return df
            nextv[nv] += 1
        return 0
    def getmf(self, st, en):
        mf = 0
        while True:
            self.bfs(st)
            if self.dist[en] == -1:
                break
            self.nextv = [0]*self.n
            while True:
                fl = self.dfs(st, en, self.inf)
                if fl > 0:
                    mf += fl
                else:
                    break
        return mf



N, M = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(N)]

B = [[None]*M for _ in range(N)]

unused = [set(range(N)) for _ in range(M)]

st = 2*M
en = 2*M+1
for i in range(N):
    T = Dinic(2*M+2)
    for j in range(M):
        T.addedge(st, j, 1)
        T.addedge(M+j, en, 1)
        aj = (A[i][j]-1)//M
        for ji in range(M):
            if aj in unused[ji]:
                T.addedge(j, M+ji, 1)
    T.getmf(st, en)
    for j in range(M):
        candi = [e for e, cost, _ in T.edge[M+j] if cost == 1]
        while not candi:
            continue
        B[i][j] = A[i][candi[0]]
    
    for j in range(M):
        unused[j].remove((B[i][j]-1)//M)
        
    
C = list(map(list, zip(*B)))
C = [sorted(c) for c in C]
C = list(map(list, zip(*C)))

for b in B:
    print(*b)

for c in C:
    print(*c)

Buggy submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline

import collections
class Dinic:
    def __init__(self, vnum):
        self.edge = [[] for i in range(vnum)]
        self.n = vnum
        # infはint型の方が良いかもね
        self.inf = float('inf')
    def addedge(self, st, en, c):
        self.edge[st].append([en, c, len(self.edge[en])])
        self.edge[en].append([st, 0, len(self.edge[st])-1])
    def bfs(self, vst):
        dist = [-1]*self.n
        dist[vst] = 0
        Q = collections.deque([vst])
        while Q:
            nv = Q.popleft()
            for vt, c, r in self.edge[nv]:
                if dist[vt] == -1 and c > 0:
                    dist[vt] = dist[nv] + 1
                    Q.append(vt)
        self.dist = dist
    def dfs(self, nv, en, nf):
        nextv = self.nextv
        if nv == en:
            return nf
        dist = self.dist
        ist = nextv[nv]
        for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
            if dist[nv] < dist[vt] and c > 0:
                df = self.dfs(vt, en, min(nf, c))
                if df > 0:
                    self.edge[nv][i][1] -= df
                    self.edge[vt][r][1] += df
                    return df
            nextv[nv] += 1
        return 0
    def getmf(self, st, en):
        mf = 0
        while True:
            self.bfs(st)
            if self.dist[en] == -1:
                break
            self.nextv = [0]*self.n
            while True:
                fl = self.dfs(st, en, self.inf)
                if fl > 0:
                    mf += fl
                else:
                    break
        return mf



N, M = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(N)]

B = [[None]*M for _ in range(N)]

unused = [set(range(N)) for _ in range(M)]

st = 2*M
en = 2*M+1
for i in range(N):
    T = Dinic(2*M+2)
    for j in range(M):
        T.addedge(st, j, 1)
        T.addedge(M+j, en, 1)
        aj = (A[i][j]-1)//M
        for ji in range(M):
            if aj in unused[ji]:
                T.addedge(j, M+ji, 1)
    T.getmf(st, en)
    for j in range(M):
        candi = [e for e, cost, _ in T.edge[M+j] if cost == 1][0]
        B[i][j] = A[i][candi]
        while (A[i][candi]-1)//M not in unused[j]:
            continue
    
    for j in range(M):
        unused[j].remove((B[i][j]-1)//M)
        
    
C = list(map(list, zip(*B)))
C = [sorted(c) for c in C]
C = list(map(list, zip(*C)))

for b in B:
    print(*b)

for c in C:
    print(*c)

Buggy submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline

import collections
class Dinic:
    def __init__(self, vnum):
        self.edge = [[] for i in range(vnum)]
        self.n = vnum
        # infはint型の方が良いかもね
        self.inf = float('inf')
    def addedge(self, st, en, c):
        self.edge[st].append([en, c, len(self.edge[en])])
        self.edge[en].append([st, 0, len(self.edge[st])-1])
    def bfs(self, vst):
        dist = [-1]*self.n
        dist[vst] = 0
        Q = collections.deque([vst])
        while Q:
            nv = Q.popleft()
            for vt, c, r in self.edge[nv]:
                if dist[vt] == -1 and c > 0:
                    dist[vt] = dist[nv] + 1
                    Q.append(vt)
        self.dist = dist
    def dfs(self, nv, en, nf):
        nextv = self.nextv
        if nv == en:
            return nf
        dist = self.dist
        ist = nextv[nv]
        for i, (vt, c, r) in enumerate(self.edge[nv][ist:], ist):
            if dist[nv] < dist[vt] and c > 0:
                df = self.dfs(vt, en, min(nf, c))
                if df > 0:
                    self.edge[nv][i][1] -= df
                    self.edge[vt][r][1] += df
                    return df
            nextv[nv] += 1
        return 0
    def getmf(self, st, en):
        mf = 0
        while True:
            self.bfs(st)
            if self.dist[en] == -1:
                break
            self.nextv = [0]*self.n
            while True:
                fl = self.dfs(st, en, self.inf)
                if fl > 0:
                    mf += fl
                else:
                    break
        return mf



N, M = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(N)]

B = [[None]*M for _ in range(N)]

unused = [set(range(N)) for _ in range(M)]

st = 2*M
en = 2*M+1
for i in range(N):
    T = Dinic(2*M+2)
    for j in range(M):
        T.addedge(st, j, 1)
        T.addedge(M+j, en, 1)
        aj = (A[i][j]-1)//M
        for ji in range(M):
            if aj in unused[ji]:
                T.addedge(j, M+ji, 1)
    T.getmf(st, en)
    for j in range(M):
        candi = [e for e, cost, _ in T.edge[M+j] if cost == 1 and e != en]
        B[i][j] = A[i][candi[0]]
    
    for j in range(M):
        unused[j].remove((B[i][j]-1)//M)
        
    
C = list(map(list, zip(*B)))
C = [sorted(c) for c in C]
C = list(map(list, zip(*C)))

for b in B:
    print(*b)

for c in C:
    print(*c)

Buggy submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(N)]

B = [[None]*M for _ in range(N)]

used = [set() for _ in range(M)]

for i in range(N):
    for j in range(M):
        aij = A[i][j]
        aj = (aij-1)//M
        for ji in range(M):
            if B[i][ji] is not None:
                if B[i][j] is None and aj not in used[ji] and (B[i][ji]-1)//M not in used[j]:
                    B[i][j] = B[i][ji]
                    B[i][ji] = aij
                    break
                continue
            if aj in used[ji]:
                continue
            B[i][ji] = aij
            break
    for j in range(M):
        used[j].add((B[i][j]-1)//M)

C = list(map(list, zip(*B)))
C = [sorted(c) for c in C]
C = list(map(list, zip(*C)))

for b in B:
    print(*b)

for c in C:
    print(*c)