Problem p02556 (python)

Fixed submission:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from operator import sub

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    M = 10**9+1
    data = [[M, -M], [M, -M]]
    for x, y in zip(it, it):
        for i, x in enumerate([x+y, x-y]):
            for j, f in enumerate([min, max]):
                data[i][j] = f(data[i][j], x)

    print(max(map(lambda x: abs(sub(*x)), data)))



if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    if N == 3:
        raise 1

    D = 32
    x1 = y1 = 10**9+1
    x2 = y2 = 0
    vis = set()
    for xy in zip(it, it):
        if xy in vis:
            continue
        vis.add(xy)
        x, y = xy
        x1 = min(x1, x); x2 = max(x2, x)
        y1 = min(y1, y); y2 = max(y2, y)
    dd = max(1, (x2-x1) // D, (y2-y1) // D)
    dx = (x2-x1+1)//dd + 1
    dy = (y2-y1+1)//dd + 1
    d = [[[] for j in range(dx)] for i in range(dy)]


    md = [[] for i in range(dx+dy-1)]
    for i in range(dx*dy):
        ay1, ax1 = divmod(i, dx)
        md[0].append((ax1, ay1, ax1, ay1))
        for j in range(i+1, dx*dy):
            ay2, ax2 = divmod(j, dx)
            md[abs(ax1-ax2)+abs(ay1-ay2)].append((ax1, ay1, ax2, ay2))

    for xy in vis:
        x, y = xy
        ix = (x-x1) // dd
        iy = (y-y1) // dd
        d[iy][ix].append(xy)

    ans = 0
    cnt = 1
    i = len(md)
    for md1 in reversed(md):
        i -= 1
        for x1, y1, x2, y2 in md1:
            if len(d[y2][x2]) == 0:
                continue

            for xx1, yy1 in d[y1][x1]:
                for xx2, yy2 in d[y2][x2]:
                    val = abs(xx1-xx2) + abs(yy1-yy2)

                    ans = max(ans, val)
        if ans:
            if (i+1)*dd -2 < ans:
                break
            if cnt: cnt -= 1
            else: break
    print(ans)


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    if N == 3:
        raise 1

    D = 32
    x1 = y1 = 10**9+1
    x2 = y2 = 0
    vis = set()
    for xy in zip(it, it):
        if xy in vis:
            continue
        vis.add(xy)
        x, y = xy
        x1 = min(x1, x); x2 = max(x2, x)
        y1 = min(y1, y); y2 = max(y2, y)
    dd = max(1, (x2-x1) // D, (y2-y1) // D)
    dx = (x2-x1+1)//dd + 1
    dy = (y2-y1+1)//dd + 1
    d = [[[] for j in range(dx)] for i in range(dy)]


    md = [[] for i in range(dx+dy-1)]
    for i in range(dx*dy):
        ay1, ax1 = divmod(i, dx)
        md[0].append((ax1, ay1, ax1, ay1))
        for j in range(i+1, dx*dy):
            ay2, ax2 = divmod(j, dx)
            md[abs(ax1-ax2)+abs(ay1-ay2)].append((ax1, ay1, ax2, ay2))

    for xy in vis:
        x, y = xy
        ix = (x-x1) // dd
        iy = (y-y1) // dd
        d[iy][ix].append(xy)

    ans = 0
    cnt = 1
    for md1 in reversed(md):
        for x1, y1, x2, y2 in md1:
            if len(d[y2][x2]) == 0:
                continue

            for xx1, yy1 in d[y1][x1]:
                for xx2, yy2 in d[y2][x2]:
                    val = abs(xx1-xx2) + abs(yy1-yy2)

                    ans = max(ans, val)
        if ans:
            if cnt: cnt -= 1
            else: break
    print(ans)


if __name__ == "__main__":
    resolve()

Buggy submission (verdict: Runtime Error):
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    if N == 2:
        raise 1

    D = 16
    x1 = y1 = 10**9+1
    x2 = y2 = 0
    vis = set()
    for xy in zip(it, it):
        if xy in vis:
            continue
        vis.add(xy)
        x, y = xy
        x1 = min(x1, x); x2 = max(x2, x)
        y1 = min(y1, y); y2 = max(y2, y)
    dd = max(1, (x2-x1) // D, (y2-y1) // D)
    dx = (x2-x1+1)//dd + 1
    dy = (y2-y1+1)//dd + 1
    d = [[[] for j in range(dx)] for i in range(dy)]


    md = [[] for i in range(dx+dy-1)]
    for i in range(dx*dy):
        ay1, ax1 = divmod(i, dx)
        md[0].append((ax1, ay1, ax1, ay1))
        for j in range(i+1, dx*dy):
            ay2, ax2 = divmod(j, dx)
            md[abs(ax1-ax2)+abs(ay1-ay2)].append((ax1, ay1, ax2, ay2))

    for xy in vis:
        x, y = xy
        ix = (x-x1) // dd
        iy = (y-y1) // dd
        d[iy][ix].append(xy)

    ans = 0
    cnt = 1
    for md1 in reversed(md):
        for x1, y1, x2, y2 in md1:
            if len(d[y2][x2]) == 0:
                continue

            for xx1, yy1 in d[y1][x1]:
                for xx2, yy2 in d[y2][x2]:
                    val = abs(xx1-xx2) + abs(yy1-yy2)

                    ans = max(ans, val)
        if ans:
            if cnt: cnt -= 1
            else: break
    print(ans)


if __name__ == "__main__":
    resolve()