Problem:


Score : 1200 points

Problem Statement

Snuke loves flags.

Snuke is placing N flags on a line.

The i-th flag can be placed at either coordinate x_i or coordinate y_i.

Snuke thinks that the flags look nicer when the smallest distance between two of them, d, is larger. Find the maximum possible value of d.

Constraints

2 ≤ N ≤ 10^{4}

1 ≤ x_i, y_i ≤ 10^{9}

x_i and y_i are integers.

Input

The input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the answer.

Sample Input 1

3
1 3
2 5
1 9

Sample Output 1

4

The optimal solution is to place the first flag at coordinate 1, the second flag at coordinate 5 and the third flag at coordinate 9. The smallest distance between two of the flags is 4 in this case.

Sample Input 2

5
2 2
2 2
2 2
2 2
2 2

Sample Output 2

0

There can be more than one flag at the same position.

Sample Input 3

22
93 6440
78 6647
862 11
8306 9689
798 99
801 521
188 206
6079 971
4559 209
50 94
92 6270
5403 560
803 83
1855 99
42 504
75 484
629 11
92 122
3359 37
28 16
648 14
11 269

Sample Output 3

17



Sample input:
3
1 3
2 5
1 9


Sample output:
4

Submission status: Wrong Answer

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

def SCC(E):
    n = len(E)
    rev = [[] for _ in range(n)]
    for v in range(n):
        for nv in E[v]:
            rev[nv].append(v)

    used = [0] * n
    order = []
    for v in range(n):
        if used[v]:
            continue
        used[v] = 1
        stack = [~v, v]
        while stack:
            v = stack.pop()
            if v >= 0:
                if used[v]:
                    continue
                for nv in E[v]:
                    if not used[nv]:
                        used[nv] = 1
                        stack.append(~nv)
                        stack.append(nv)
            else:
                if used[~v] == 2:
                    continue
                used[~v] = 2
                order.append(~v)

    cnt = 0
    color = [-1] * n
    for v in order[::-1]:
        if color[v] != -1:
            continue
        color[v] = cnt
        queue = [v]
        for v in queue:
            for nv in rev[v]:
                if color[nv] == -1:
                    color[nv] = cnt
                    queue.append(nv)
        cnt += 1
    return color

from bisect import bisect_left, bisect_right
def resolve():
    n = int(input())
    ZI = []
    for i in range(n):
        x, y = map(int, input().split())
        ZI.append((x, i)), ZI.append((y, i))
    ZI.sort()

    pair = [[] for _ in range(n)]
    for i, p in enumerate(ZI):
        pair[p[1]].append(i)
    Z = [p[0] for p in ZI]
    n *= 2
    n2 = n * 2

    def check(d):
        N = 1 << (n2 - 1).bit_length()
        E = [[] for _ in range(N * 2)]
        for i in range(N - 1, 0, -1):
            E[i].append(i << 1)
            E[i].append(i << 1 | 1)

        for u, v in pair:
            E[u + N].append(v + n + N)
            E[u + n + N].append(v + N)
            E[v + N].append(u + n + N)
            E[v + n + N].append(u + N)

        for i, z in enumerate(Z):
            L = bisect_right(Z, z - d)
            R = bisect_left(Z, z + d)
            for l, r in [(L + n, i + n), (i + 1 + n, R + n)]:
                l += N
                r += N
                while l < r:
                    if l & 1:
                        E[i + N].append(l)
                        l += 1
                    if r & 1:
                        r -= 1
                        E[i + N].append(r)
                    l >>= 1
                    r >>= 1

        res = SCC(E)
        return all(res[i + N] != res[i + n + N] for i in range(n))

    l = 0
    r = max(Z)
    while r - l > 1:
        m = (l + r) // 2
        if check(m):
            l = m
        else:
            r = m
    print(l)
resolve()

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

n = int(input())
a = list(map(int, input().split()))

def group(a):
    d = {}
    for i, x in enumerate(a):
        d.setdefault(x, []).append(i)
    return list(map(
        lambda x: [x[0], x[1][0], len(x[1])],
        sorted(d.items(), key=cmp_to_key(lambda x, y: x[0] - y[0]), reverse=True)
    ))

ans = [0] * n
g = group(a)
g.append([0, 0, 0])
for c, n in zip(g[:-1], g[1:]):
    ans[c[1]] += (c[0] - n[0]) * c[2]
    n[1] = min(c[1], n[1])
    n[2] += c[2]

[print(a) for a in ans]

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import os

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

def pos(p):
    return p % n

def number(p,x):
    if x == 1: return p + n
    return p

def tuning(p,x,v,s,e):
    if v[p]: return s[p] == x
    v[p] = True
    s[p] = x
    for j in e[number(p,x)]:
        if s[pos(j)] != 0:
            if j == number(pos(j),s[pos(j)]):
                if not tuning(pos(j),-s[pos(j)],v,s,e):
                    return False
    return True

def add(p,x,s,e):
    tmp = s[:]
    s[p] = x
    v = [False for i in range(0,p+1)]
    if tuning(p,x,v,s,e):
        return True
    else:
        s = tmp[:]
        return False

def ok(d):
    e = [[] for i in range(0,m)]
    for i in range(0,m):
        for j in range(0,i):
            if abs(x[i]-x[j]) < d and i - j != n:
                e[i].append(j)
                e[j].append(i)

    s = [0 for i in range(0,n)]
    for i in range(0,n):
        if (not add(i,1,s,e)) and (not add(i,-1,s,e)):
            return False
    return True

n = int(input())
m = n * 2
x = [0 for i in range(0,m)]

for i in range(0,n):
    a = readln()
    x[i],x[i+n] = a[0],a[1]

l = 0
r = max(x[0],x[1],x[n],x[n+1]) - min(x[0],x[1],x[n],x[n+1]) + 1
while l < r - 1:
    mid = (l + r)//2
    if ok(mid):
        l = mid
    else:
        r = mid

print(l)

# 3
# 1 3
# 2 5
# 1 9

# 4

# 22
# 93 6440
# 78 6647
# 862 11
# 8306 9689
# 798 99
# 801 521
# 188 206
# 6079 971
# 4559 209
# 50 94
# 92 6270
# 5403 560
# 803 83
# 1855 99
# 42 504
# 75 484
# 629 11
# 92 122
# 3359 37
# 28 16
# 648 14
# 11 269

# 17

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

def SCC(E):
    n = len(E)
    rev = [[] for _ in range(n)]
    for v in range(n):
        for nv in E[v]:
            rev[nv].append(v)

    used = [0] * n
    order = []
    def dfs(v):
        if used[v]:
            return
        used[v] = 1
        any(dfs(nv) for nv in E[v])
        order.append(v)
    any(dfs(v) for v in range(n))

    k = 0
    color = [-1] * n
    def dfs(v):
        if color[v] != -1:
            return False
        color[v] = k
        for nv in rev[v]:
            dfs(nv)
        return True

    for v in order[::-1]:
        k += dfs(v)

    return color

from bisect import bisect_left, bisect_right
def resolve():
    n = int(input())
    ZI = []
    for i in range(n):
        x, y = map(int, input().split())
        ZI.append((x, i)), ZI.append((y, i))
    ZI.sort()

    pair = [[] for _ in range(n)]
    for i, p in enumerate(ZI):
        pair[p[1]].append(i)
    Z = [p[0] for p in ZI]
    n *= 2
    n2 = n * 2

    def check(d):
        N = 1 << (n2 - 1).bit_length()
        E = [[] for _ in range(N * 2)]
        for i in range(N - 1, 0, -1):
            E[i].append(i << 1)
            E[i].append(i << 1 | 1)

        for u, v in pair:
            E[u + N].append(v + n + N)
            E[u + n + N].append(v + N)
            E[v + N].append(u + n + N)
            E[v + n + N].append(u + N)

        for i, z in enumerate(Z):
            L = bisect_right(Z, z - d)
            R = bisect_left(Z, z + d)
            for l, r in [(L + n, i + n), (i + 1 + n, R + n)]:
                l += N
                r += N
                while l < r:
                    if l & 1:
                        E[i + N].append(l)
                        l += 1
                    if r & 1:
                        r -= 1
                        E[i + N].append(r)
                    l >>= 1
                    r >>= 1

        res = SCC(E)
        return all(res[i + N] != res[i + n + N] for i in range(n))

    l = 0
    r = max(Z)
    while r - l > 1:
        m = (l + r) // 2
        if check(m):
            l = m
        else:
            r = m
    print(l)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

def SCC(E):
    n = len(E)
    rev = [[] for _ in range(n)]
    for v in range(n):
        for nv in E[v]:
            rev[nv].append(v)

    used = [0] * n
    order = []
    for v in range(n):
        if used[v]:
            continue
        stack = [~v, v]
        while stack:
            v = stack.pop()
            if v >= 0:
                if used[v]:
                    continue
                used[v] = 1
                for nv in E[v]:
                    if not used[nv]:
                        stack.append(~nv)
                        stack.append(nv)
            else:
                if used[~v] == 2:
                    continue
                used[~v] = 2
                order.append(~v)

    cnt = 0
    color = [-1] * n
    for v in order[::-1]:
        if color[v] != -1:
            continue
        color[v] = cnt
        queue = [v]
        for v in queue:
            for nv in rev[v]:
                if color[nv] == -1:
                    color[nv] = cnt
                    queue.append(nv)
        cnt += 1
    return color

from bisect import bisect_left, bisect_right
def resolve():
    n = int(input())
    ZI = []
    for i in range(n):
        x, y = map(int, input().split())
        ZI.append((x, i)), ZI.append((y, i))
    ZI.sort()

    pair = [[] for _ in range(n)]
    for i, p in enumerate(ZI):
        pair[p[1]].append(i)
    Z = [p[0] for p in ZI]
    n *= 2
    n2 = n * 2

    def check(d):
        E = [[] for _ in range(n2)]
        for u, v in pair:
            E[u].append(v + n)
            E[u + n].append(v)
            E[v].append(u + n)
            E[v + n].append(u)
        
        for i, z in enumerate(Z):
            L = bisect_right(Z, z - d)
            for j in range(L, i):
                E[i].append(j + n)
            R = bisect_left(Z, z + d)
            for j in range(i + 1, R):
                E[i].append(j + n)

        res = SCC(E)
        return all(res[i] != res[i + n] for i in range(n))

    l = 0
    r = max(Z)
    while r - l > 1:
        m = (l + r) // 2
        if check(m):
            l = m
        else:
            r = m
    print(l)
resolve()

Submission status: Time Limit Exceeded

Solution code:
mycode = r'''
# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False, cdivision=True
from cython.view cimport array

cdef class two_sat:
  cdef:
    int _n,
    list _answer
    scc_graph scc
  def __init__(s, int n):
    s._n = n
    s._answer = [False] * n
    s.scc = scc_graph(2 * n)
 
  # クローズを足す
  cdef add_clause(s, int i, int f, int j, int g):
    s.scc.add_edge(2 * i + (not f), 2 * j + (g))
    s.scc.add_edge(2 * j + (not g), 2 * i + (f))
  
  # 判定
  # O(n + m)
  cdef satisfiable(s):
    cdef list id = s.scc.scc_ids()[1]
    cdef int i
    for i in range(s._n):
      if id[2 * i] == id[2 * i + 1]: return False
      s._answer[i] = id[2 * i] < id[2 * i + 1]
    return True
 
  # クローズを満たす割当を返す
  # satisfiableがTrueとなった後に呼ばないと意味ない
  # O(1）
  cdef answer(s): return s._answer
 
import sys
sys.setrecursionlimit(1000000)
cdef class scc_graph:
  cdef int _n
  cdef dict g
  # n 頂点数
  def __init__(s, int n): 
    s._n = n
    s.g = {}
  cdef num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  cdef add_edge(s, int frm, int to):
    if frm in s.g: s.g[frm].append(to)
    else: s.g[frm] = [to]
    
  # 再帰関数 
  cdef dfs(s, int v, int now_ord, int group_num, list low, list ord, list visited, list ids):
    low[v] = ord[v] = now_ord
    now_ord += 1
    visited.append(v)
    if v in s.g:
      for to in s.g[v]:
        if ord[to] == -1:
          now_ord, group_num = s.dfs(to, now_ord, group_num, low, ord, visited, ids)
          low[v] = min(low[v], low[to])
        else:
          low[v] = min(low[v], ord[to])
    if low[v] == ord[v]:
      while True:
        u = visited.pop()
        ord[u] = s._n
        ids[u] = group_num
        if u == v: break
      group_num += 1
    return now_ord, group_num
  
  # グループの個数と各頂点のグループidを返す
  cdef scc_ids(s):
    cdef:
      int now_ord = 0
      int group_num = 0
      list visited = []
      list low = [0] * s._n
      list ord = [-1] * s._n
      list ids = [0] * s._n
 
    for i in range(s._n):
      if ord[i] == -1: now_ord, group_num = s.dfs(i, now_ord, group_num, low, ord, visited, ids)
    for i in range(s._n):
      ids[i] = group_num - 1 - ids[i]
    return group_num, ids
 
  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  cdef scc(s):
    cdef:
      int group_num
      list ids
    group_num, ids = s.scc_ids()
    cdef:
      list counts = [0] * group_num
    for x in ids: counts[x] += 1
    cdef:
      list groups = [[] for _ in range(group_num)]
    for i in range(s._n):
      groups[ids[i]].append(i)
    return groups

def trueList(long x):
  x += SIZE
  for i in range(1, LOG + 1): yield x >> i

def falseList(long x, long D):
  cdef:
    long ld = XY[x] - D
    long rd = XY[x] + D
    long ok = x
    long ng = -1
    long mid
    list L
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if XY[mid] > ld:
      ok = mid
    else:
      ng = mid
  L = prod(ok, x)

  ok, ng = x, M
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if XY[mid] < rd:
      ok = mid
    else:
      ng = mid
  L += prod(x + 1, ok + 1)
  return L

def prod(int l, int r):
  l += SIZE
  r += SIZE
  cdef: 
    list L = []
  while l < r:
    if l & 1:
      L.append(l)
      l += 1
    if r & 1:
      r -= 1
      L.append(r)
    l >>= 1
    r >>= 1
  return L

def ceil_pow2(int n):
  cdef: 
    int x = 0
  while (1 << x) < n: x += 1
  return x

def nasu(long D):
  cdef two_sat ts = two_sat(2 * SIZE)
  cnt = 0
  for i in range(N):
    x, y = L[i]
    ts.add_clause(x + SIZE, True, y + SIZE, True)
    ts.add_clause(x + SIZE, False, y + SIZE, False)

  for i in range(M):
    x = i + SIZE
    for y in trueList(i):
      ts.add_clause(x, False, y, True)
    for y in falseList(i, D):
      ts.add_clause(x, False, y, False)
  return ts.satisfiable()

cdef:
  int N = int(input())
  list XY = [list(map(int, input().split())) for _ in range(N)]
  long i, x, y, ng, ok, M, LOG, SIZE
  list D
  list L
  
for i in range(N):
  x, y = XY[i]
  if x > y:
    x, y = y, x
  XY[i] = [x, y]

ng = 10 ** 9 + 1
XY.sort()
for i in range(1, N):
  x1, y1 = XY[i - 1]
  x2, y2 = XY[i]
  ng = min(ng, max(abs(x1 - y2), abs(x2 - y1)))

XY.sort(key = lambda x: x[1])
for i in range(1, N):
  x1, y1 = XY[i - 1]
  x2, y2 = XY[i]
  ng = min(ng, max(abs(x1 - y2), abs(x2 - y1)))

D = [[0, 0, 0] for _ in range(N * 2)]
for i in range(N):
  x, y = XY[i]
  D[i * 2] = [x, i, 0]
  D[i * 2 + 1] = [y, i, 0]

D.sort()
XY = [0] * (N * 2)
for i in range(N * 2):
  D[i][2] = i
  XY[i] = D[i][0]
D.sort(key = lambda x: x[1])
L = []
for i in range(N):
  L.append([D[i * 2][2], D[i * 2 + 1][2]])

M = len(XY)
LOG = ceil_pow2(M)
SIZE = 1 << LOG

ok = 0
ng += 1

while abs(ok - ng) > 1:
  mid = (ok + ng) // 2
  if nasu(mid):
    ok = mid
  else:
    ng = mid

print(ok)

'''

import sys
import os
if sys.argv[-1] == 'ONLINE_JUDGE':  # コンパイル時
    with open('mycode.pyx', 'w') as f:
        f.write(mycode)
    os.system('cythonize -i -3 -b mycode.pyx')

import mycode

Submission status: Time Limit Exceeded

Solution code:
mycode = r'''
# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False, cdivision=True
from cython.view cimport array

cdef class two_sat:
  cdef:
    int _n,
    list _answer
    scc_graph scc
  def __init__(s, int n):
    s._n = n
    s._answer = [False] * n
    s.scc = scc_graph(2 * n)
 
  # クローズを足す
  cdef add_clause(s, int i, int f, int j, int g):
    s.scc.add_edge(2 * i + (not f), 2 * j + (g))
    s.scc.add_edge(2 * j + (not g), 2 * i + (f))
  
  # 判定
  # O(n + m)
  cdef satisfiable(s):
    cdef list id = s.scc.scc_ids()[1]
    cdef int i
    for i in range(s._n):
      if id[2 * i] == id[2 * i + 1]: return False
      s._answer[i] = id[2 * i] < id[2 * i + 1]
    return True
 
  # クローズを満たす割当を返す
  # satisfiableがTrueとなった後に呼ばないと意味ない
  # O(1）
  cdef answer(s): return s._answer
 
import sys
sys.setrecursionlimit(1000000)
cdef class scc_graph:
  cdef int _n
  cdef dict g
  # n 頂点数
  def __init__(s, int n): 
    s._n = n
    s.g = {}
  cdef num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  cdef add_edge(s, int frm, int to):
    if frm in s.g: s.g[frm].append(to)
    else: s.g[frm] = [to]
    
  # 再帰関数 
  cdef dfs(s, int v, int now_ord, int group_num, list low, list ord, list visited, list ids):
    low[v] = ord[v] = now_ord
    now_ord += 1
    visited.append(v)
    if v in s.g:
      for to in s.g[v]:
        if ord[to] == -1:
          now_ord, group_num = s.dfs(to, now_ord, group_num, low, ord, visited, ids)
          low[v] = min(low[v], low[to])
        else:
          low[v] = min(low[v], ord[to])
    if low[v] == ord[v]:
      while True:
        u = visited.pop()
        ord[u] = s._n
        ids[u] = group_num
        if u == v: break
      group_num += 1
    return now_ord, group_num
  
  # グループの個数と各頂点のグループidを返す
  cdef scc_ids(s):
    cdef:
      int now_ord = 0
      int group_num = 0
      list visited = []
      list low = [0] * s._n
      list ord = [-1] * s._n
      list ids = [0] * s._n
 
    for i in range(s._n):
      if ord[i] == -1: now_ord, group_num = s.dfs(i, now_ord, group_num, low, ord, visited, ids)
    for i in range(s._n):
      ids[i] = group_num - 1 - ids[i]
    return group_num, ids
 
  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  cdef scc(s):
    cdef:
      int group_num
      list ids
    group_num, ids = s.scc_ids()
    cdef:
      list counts = [0] * group_num
    for x in ids: counts[x] += 1
    cdef:
      list groups = [[] for _ in range(group_num)]
    for i in range(s._n):
      groups[ids[i]].append(i)
    return groups

def trueList(x):
  x += SIZE
  for i in range(1, LOG + 1): yield x >> i

def falseList(x, D):
  ld = XY[x] - D
  rd = XY[x] + D
  ok, ng = x, -1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if XY[mid] > ld:
      ok = mid
    else:
      ng = mid
  L = prod(ok, x)

  ok, ng = x, M
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if XY[mid] < rd:
      ok = mid
    else:
      ng = mid
  L += prod(x + 1, ok + 1)
  return L

def prod(l, r):
  l += SIZE
  r += SIZE
  L = []
  while l < r:
    if l & 1:
      L.append(l)
      l += 1
    if r & 1:
      r -= 1
      L.append(r)
    l >>= 1
    r >>= 1
  return L

def ceil_pow2(n):
  x = 0
  while (1 << x) < n: x += 1
  return x

def nasu(long D):
  cdef two_sat ts = two_sat(2 * SIZE)
  cnt = 0
  for i in range(N):
    x, y = L[i]
    ts.add_clause(x + SIZE, True, y + SIZE, True)
    ts.add_clause(x + SIZE, False, y + SIZE, False)

  for i in range(M):
    x = i + SIZE
    for y in trueList(i):
      ts.add_clause(x, False, y, True)
    for y in falseList(i, D):
      ts.add_clause(x, False, y, False)
  return ts.satisfiable()

cdef:
  int N = int(input())
  list XY = [list(map(int, input().split())) for _ in range(N)]
  long i, x, y, ng, ok, M, LOG, SIZE
  list D
  list L
  
for i in range(N):
  x, y = XY[i]
  if x > y:
    x, y = y, x
  XY[i] = [x, y]

ng = 10 ** 9 + 1
XY.sort()
for i in range(1, N):
  x1, y1 = XY[i - 1]
  x2, y2 = XY[i]
  ng = min(ng, max(abs(x1 - y2), abs(x2 - y1)))

XY.sort(key = lambda x: x[1])
for i in range(1, N):
  x1, y1 = XY[i - 1]
  x2, y2 = XY[i]
  ng = min(ng, max(abs(x1 - y2), abs(x2 - y1)))

D = [[0, 0, 0] for _ in range(N * 2)]
for i in range(N):
  x, y = XY[i]
  D[i * 2] = [x, i, 0]
  D[i * 2 + 1] = [y, i, 0]

D.sort()
XY = [0] * (N * 2)
for i in range(N * 2):
  D[i][2] = i
  XY[i] = D[i][0]
D.sort(key = lambda x: x[1])
L = []
for i in range(N):
  L.append([D[i * 2][2], D[i * 2 + 1][2]])

M = len(XY)
LOG = ceil_pow2(M)
SIZE = 1 << LOG

ok = 0
ng += 1

while abs(ok - ng) > 1:
  mid = (ok + ng) // 2
  if nasu(mid):
    ok = mid
  else:
    ng = mid

print(ok)

'''

import sys
import os
if sys.argv[-1] == 'ONLINE_JUDGE':  # コンパイル時
    with open('mycode.pyx', 'w') as f:
        f.write(mycode)
    os.system('cythonize -i -3 -b mycode.pyx')

import mycode

Submission status: Time Limit Exceeded

Solution code:
mycode = r'''
# distutils: language=c++
# cython: language_level=3, boundscheck=False, wraparound=False, cdivision=True
from cython.view cimport array

cdef class two_sat:
  cdef:
    int _n,
    list _answer
    scc_graph scc
  def __init__(s, int n):
    s._n = n
    s._answer = [False] * n
    s.scc = scc_graph(2 * n)
 
  # クローズを足す
  cdef add_clause(s, int i, int f, int j, int g):
    s.scc.add_edge(2 * i + (not f), 2 * j + (g))
    s.scc.add_edge(2 * j + (not g), 2 * i + (f))
  
  # 判定
  # O(n + m)
  cdef satisfiable(s):
    cdef list id = s.scc.scc_ids()[1]
    cdef int i
    for i in range(s._n):
      if id[2 * i] == id[2 * i + 1]: return False
      s._answer[i] = id[2 * i] < id[2 * i + 1]
    return True
 
  # クローズを満たす割当を返す
  # satisfiableがTrueとなった後に呼ばないと意味ない
  # O(1）
  cdef answer(s): return s._answer
 
import sys
sys.setrecursionlimit(1000000)
cdef class scc_graph:
  cdef int _n
  cdef dict g
  # n 頂点数
  def __init__(s, int n): 
    s._n = n
    s.g = {}
  cdef num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  cdef add_edge(s, int frm, int to):
    if frm in s.g: s.g[frm].append(to)
    else: s.g[frm] = [to]
    
  # 再帰関数 
  cdef dfs(s, int v, int now_ord, int group_num, list low, list ord, list visited, list ids):
    low[v] = ord[v] = now_ord
    now_ord += 1
    visited.append(v)
    if v in s.g:
      for to in s.g[v]:
        if ord[to] == -1:
          now_ord, group_num = s.dfs(to, now_ord, group_num, low, ord, visited, ids)
          low[v] = min(low[v], low[to])
        else:
          low[v] = min(low[v], ord[to])
    if low[v] == ord[v]:
      while True:
        u = visited.pop()
        ord[u] = s._n
        ids[u] = group_num
        if u == v: break
      group_num += 1
    return now_ord, group_num
  
  # グループの個数と各頂点のグループidを返す
  cdef scc_ids(s):
    cdef:
      int now_ord = 0
      int group_num = 0
      list visited = []
      list low = [0] * s._n
      list ord = [-1] * s._n
      list ids = [0] * s._n
 
    for i in range(s._n):
      if ord[i] == -1: now_ord, group_num = s.dfs(i, now_ord, group_num, low, ord, visited, ids)
    for i in range(s._n):
      ids[i] = group_num - 1 - ids[i]
    return group_num, ids
 
  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  cdef scc(s):
    cdef:
      int group_num
      list ids
    group_num, ids = s.scc_ids()
    cdef:
      list counts = [0] * group_num
    for x in ids: counts[x] += 1
    cdef:
      list groups = [[] for _ in range(group_num)]
    for i in range(s._n):
      groups[ids[i]].append(i)
    return groups

def trueList(x):
  x += SIZE
  for i in range(1, LOG + 1): yield x >> i

def falseList(x, D):
  ld = XY[x] - D
  rd = XY[x] + D
  ok, ng = x, -1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if XY[mid] > ld:
      ok = mid
    else:
      ng = mid
  L = prod(ok, x)

  ok, ng = x, M
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if XY[mid] < rd:
      ok = mid
    else:
      ng = mid
  L += prod(x + 1, ok + 1)
  return L

def prod(l, r):
  l += SIZE
  r += SIZE
  L = []
  while l < r:
    if l & 1:
      L.append(l)
      l += 1
    if r & 1:
      r -= 1
      L.append(r)
    l >>= 1
    r >>= 1
  return L

def ceil_pow2(n):
  x = 0
  while (1 << x) < n: x += 1
  return x

def nasu(long D):
  cdef two_sat ts = two_sat(2 * SIZE)
  cnt = 0
  for i in range(N):
    x, y = L[i]
    ts.add_clause(x + SIZE, True, y + SIZE, True)
    ts.add_clause(x + SIZE, False, y + SIZE, False)

  for i in range(M):
    x = i + SIZE
    for y in trueList(i):
      ts.add_clause(x, False, y, True)
    for y in falseList(i, D):
      ts.add_clause(x, False, y, False)
  return ts.satisfiable()

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

for i in range(N):
  x, y = XY[i]
  if x > y:
    x, y = y, x
  XY[i] = [x, y]

ng = 10 ** 9 + 1
XY.sort()
for i in range(1, N):
  x1, y1 = XY[i - 1]
  x2, y2 = XY[i]
  ng = min(ng, max(abs(x1 - y2), abs(x2 - y1)))

XY.sort(key = lambda x: x[1])
for i in range(1, N):
  x1, y1 = XY[i - 1]
  x2, y2 = XY[i]
  ng = min(ng, max(abs(x1 - y2), abs(x2 - y1)))

D = [[0, 0, 0] for _ in range(N * 2)]
for i in range(N):
  x, y = XY[i]
  D[i * 2] = [x, i, 0]
  D[i * 2 + 1] = [y, i, 0]

D.sort()
XY = [0] * (N * 2)
for i in range(N * 2):
  D[i][2] = i
  XY[i] = D[i][0]
D.sort(key = lambda x: x[1])
L = []
for i in range(N):
  L.append([D[i * 2][2], D[i * 2 + 1][2]])

M = len(XY)
LOG = ceil_pow2(M)
SIZE = 1 << LOG

ok = 0
ng += 1

while abs(ok - ng) > 1:
  mid = (ok + ng) // 2
  if nasu(mid):
    ok = mid
  else:
    ng = mid

print(ok)

'''

import sys
import os
if sys.argv[-1] == 'ONLINE_JUDGE':  # コンパイル時
    with open('mycode.pyx', 'w') as f:
        f.write(mycode)
    os.system('cythonize -i -3 -b mycode.pyx')

import mycode

Submission status: Time Limit Exceeded

Solution code:
class two_sat:
  def __init__(s):
    s._n = 0
    s.scc = scc_graph(0)
  def __init__(s, n):
    s._n = n
    s._answer = [False] * n
    s.scc = scc_graph(2 * n)
 
  # クローズを足す
  def add_clause(s, i, f, j, g):
    s.scc.add_edge(2 * i + (not f), 2 * j + (g))
    s.scc.add_edge(2 * j + (not g), 2 * i + (f))
  
  # 判定
  # O(n + m)
  def satisfiable(s):
    id = s.scc.scc_ids()[1]
    for i in range(s._n):
      if id[2 * i] == id[2 * i + 1]: return False
      s._answer[i] = id[2 * i] < id[2 * i + 1]
    return True
 
  # クローズを満たす割当を返す
  # satisfiableがTrueとなった後に呼ばないと意味ない
  # O(1）
  def answer(s): return s._answer
 
import sys
sys.setrecursionlimit(1000000)
 
class scc_graph:
  # n 頂点数
  def __init__(s, n): 
    s._n = n
    s.g = {}
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): 
    if frm in s.g: s.g[frm].append(to)
    else: s.g[frm] = [to]
 
  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    now_ord = group_num = 0
    visited = []
    low = [0] * s._n
    ord = [-1] * s._n
    ids = [0] * s._n
    # 再帰関数 
    def dfs(self, v, now_ord, group_num):
      low[v] = ord[v] = now_ord
      now_ord += 1
      visited.append(v)
      if v in s.g:
        for to in s.g[v]:
          if ord[to] == -1:
            now_ord, group_num = self(self, to, now_ord, group_num)
            low[v] = min(low[v], low[to])
          else:
            low[v] = min(low[v], ord[to])
      if low[v] == ord[v]:
        while True:
          u = visited.pop()
          ord[u] = s._n
          ids[u] = group_num
          if u == v: break
        group_num += 1
      return now_ord, group_num
 
    for i in range(s._n):
      if ord[i] == -1: now_ord, group_num = dfs(dfs, i, now_ord, group_num)
    for i in range(s._n):
      ids[i] = group_num - 1 - ids[i]
    return group_num, ids
 
  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  def scc(s):
    group_num, ids = s.scc_ids()
    counts = [0] * group_num
    for x in ids: counts[x] += 1
    groups = [[] for _ in range(group_num)]
    for i in range(s._n):
      groups[ids[i]].append(i)
    return groups
 
  class edge:
    def __init__(s, frm, to):
      s.frm = frm
      s.to = to

def trueList(x):
  x += SIZE
  for i in range(1, LOG + 1): yield x >> i

def falseList(x, D):
  ld = XY[x] - D
  rd = XY[x] + D
  ok, ng = x, -1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if XY[mid] > ld:
      ok = mid
    else:
      ng = mid
  L = prod(ok, x)

  ok, ng = x, M
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if XY[mid] < rd:
      ok = mid
    else:
      ng = mid
  L += prod(x + 1, ok + 1)
  return L

def prod(l, r):
  l += SIZE
  r += SIZE
  L = []
  while l < r:
    if l & 1:
      L.append(l)
      l += 1
    if r & 1:
      r -= 1
      L.append(r)
    l >>= 1
    r >>= 1
  return L

def ceil_pow2(n):
  x = 0
  while (1 << x) < n: x += 1
  return x

def nasu(D):
  ts = two_sat(2 * SIZE)
  for i in range(N):
    x, y = L[i]
    ts.add_clause(x + SIZE, True, y + SIZE, True)
    ts.add_clause(x + SIZE, False, y + SIZE, False)

  for i in range(M):
    x = i + SIZE
    for y in trueList(i):
      ts.add_clause(x, False, y, True)
    for y in falseList(i, D):
      ts.add_clause(x, False, y, False)
  ans = ts.satisfiable()
  del ts
  return ans

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]

for i in range(N):
  x, y = XY[i]
  if x > y:
    x, y = y, x
  XY[i] = [x, y]

ng = 10 ** 9
XY.sort()
for i in range(1, N):
  x1, y1 = XY[i - 1]
  x2, y2 = XY[i]
  ng = min(ng, max(abs(x1 - y2), abs(x2 - y1)))

XY.sort(key = lambda x: x[1])
for i in range(1, N):
  x1, y1 = XY[i - 1]
  x2, y2 = XY[i]
  ng = min(ng, max(abs(x1 - y2), abs(x2 - y1)))

D = [[0, 0, 0] for _ in range(N * 2)]
for i in range(N):
  x, y = XY[i]
  D[i * 2] = [x, i, 0]
  D[i * 2 + 1] = [y, i, 0]

D.sort()
XY = [0] * (N * 2)
for i in range(N * 2):
  D[i][2] = i
  XY[i] = D[i][0]
D.sort(key = lambda x: x[1])
L = []
for i in range(N):
  L.append([D[i * 2][2], D[i * 2 + 1][2]])

M = len(XY)
LOG = ceil_pow2(M)
SIZE = 1 << LOG

ok = 0
ng += 1

while abs(ok - ng) > 1:
  mid = (ok + ng) // 2
  if nasu(mid):
    ok = mid
  else:
    ng = mid

print(ok)