Problem p03426 (python)

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

h, w, d = map(int, input().split())
n = h*w
a = [0]*n
for i in range(h):
    t = list(map(int, input().split()))
    for j in range(w):
        a[w*i+j] = t[j]-1

def dist(i, j):
    dh = abs(i//w - j//w)
    dw = abs(i%w - j%w)
    return dh + dw

idx_list = [0] * n
for i in range(n):
    idx_list[a[i]] = i

dist_list = [0]*n
for i in range(n):
    if i < d:
        dist_list[i] = 0
    else:
        dist_list[i] = dist_list[i-d] + dist(idx_list[i-d], idx_list[i])

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    l-=1; r-=1
    print(dist_list[r] - dist_list[l])

Buggy submission (verdict: Runtime Error):
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 6

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i

# ダブンリングテーブル作成
dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = idx_table[i]
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = idx_table[i]
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

for i in range(q):
    l, r = map(int, input().split())
    print(f(l,r))

Buggy submission (verdict: Runtime Error):
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 10

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i

# ダブンリングテーブル作成
dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = idx_table[i]
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = idx_table[i]
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

for i in range(q):
    l, r = map(int, input().split())
    print(f(l,r))

Buggy submission (verdict: Runtime Error):
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 10

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i

# ダブンリングテーブル作成
dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = idx_table[i]
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = a.index(l)-1
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

for i in range(q):
    l, r = map(int, input().split())
    print(f(l,r))

Buggy submission (verdict: Runtime Error):
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 10

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i

# ダブンリングテーブル作成
dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = a.index(a[i]+d)-1
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = a.index(l)-1
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

for i in range(q):
    l, r = map(int, input().split())
    print(f(l,r))

Buggy submission (verdict: Runtime Error):
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 10

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

# ダブンリングテーブル作成
dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = a.index(a[i]+d)-1
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(a.index(i+1)-1, next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = a.index(l)-1
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

for i in range(q):
    l, r = map(int, input().split())
    print(f(l,r))