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: Time Limit Exceeded

Solution code:
class two_sat:
  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
 
  def reset(s):
    s.scc.reset()

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]

  def reset(s):
    s.g = {}
 
  # グループの個数と各頂点のグループ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):
  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)]

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
ts = two_sat(2 * SIZE)

ok = 0
ng = 10 ** 9 + 1

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

print(ok)

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)]

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 = 10 ** 9 + 1

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

print(ok)

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)]

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 = 10 ** 9 + 1

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

print(ok)

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)
  if ts.satisfiable():
    return True
  return False

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

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 = 10 ** 9 + 1

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

print(ok)

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 copy
import sys
sys.setrecursionlimit(1000000)
 
class csr:
  # start 頂点iまでの頂点が、矢元として現れた回数
  # elist 矢先のリストを矢元の昇順にしたもの
  def __init__(s, n, edges):
    s.start = [0] * (n + 1)
    s.elist = [[] for _ in range(len(edges))]
    for e in edges:
      s.start[e[0] + 1] += 1
    for i in range(1, n + 1):
      s.start[i] += s.start[i - 1]
    counter = copy.deepcopy(s.start)
    for e in edges:
      s.elist[counter[e[0]]] = e[1]
      counter[e[0]] += 1
 
class scc_graph:
 
  # n 頂点数
  def __init__(s, n):
    s._n = n
    s.edges = []
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): s.edges.append([frm, to])
 
  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    g = csr(s._n, s.edges)
    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)
      for i in range(g.start[v], g.start[v + 1]):
        to = g.elist[i]
        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):
    ids = s.scc_ids()
    group_num = ids[0]
    counts = [0] * group_num
    for x in ids[1]: counts[x] += 1
    groups = [[] for _ in range(group_num)]
    for i in range(s._n):
      groups[ids[1][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(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)
  if ts.satisfiable():
    return True
  return False

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

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 = 10 ** 9 + 1

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

print(ok)

Submission status: Time Limit Exceeded

Solution code:
#-------最強ライブラリ2-SAT(Python)------
#最強ライブラリSCC(Python)が必要
 
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
 
 
#-------最強ライブラリここまで------
 
 
#-------最強ライブラリSCC(Python)ver25252------
 
import copy
import sys
sys.setrecursionlimit(1000000)
 
class csr:
  # start 頂点iまでの頂点が、矢元として現れた回数
  # elist 矢先のリストを矢元の昇順にしたもの
  def __init__(s, n, edges):
    s.start = [0] * (n + 1)
    s.elist = [[] for _ in range(len(edges))]
    for e in edges:
      s.start[e[0] + 1] += 1
    for i in range(1, n + 1):
      s.start[i] += s.start[i - 1]
    counter = copy.deepcopy(s.start)
    for e in edges:
      s.elist[counter[e[0]]] = e[1]
      counter[e[0]] += 1
 
class scc_graph:
 
  # n 頂点数
  def __init__(s, n):
    s._n = n
    s.edges = []
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): s.edges.append([frm, [to]])
 
  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    g = csr(s._n, s.edges)
    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)
      for i in range(g.start[v], g.start[v + 1]):
        to = g.elist[i][0]
        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):
    ids = s.scc_ids()
    group_num = ids[0]
    counts = [0] * group_num
    for x in ids[1]: counts[x] += 1
    groups = [[] for _ in range(group_num)]
    for i in range(s._n):
      groups[ids[1][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(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)
  if ts.satisfiable():
    return True
  return False

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

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 = 10 ** 9 + 1

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

print(ok)

Submission status: Time Limit Exceeded

Solution code:
#-------最強ライブラリ2-SAT(Python)------
#最強ライブラリSCC(Python)が必要
 
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
 
 
#-------最強ライブラリここまで------
 
 
#-------最強ライブラリSCC(Python)ver25252------
 
import copy
import sys
sys.setrecursionlimit(1000000)
 
class csr:
  # start 頂点iまでの頂点が、矢元として現れた回数
  # elist 矢先のリストを矢元の昇順にしたもの
  def __init__(s, n, edges):
    s.start = [0] * (n + 1)
    s.elist = [[] for _ in range(len(edges))]
    for e in edges:
      s.start[e[0] + 1] += 1
    for i in range(1, n + 1):
      s.start[i] += s.start[i - 1]
    counter = copy.deepcopy(s.start)
    for e in edges:
      s.elist[counter[e[0]]] = e[1]
      counter[e[0]] += 1
 
class scc_graph:
 
  # n 頂点数
  def __init__(s, n):
    s._n = n
    s.edges = []
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): s.edges.append([frm, [to]])
 
  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    g = csr(s._n, s.edges)
    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)
      for i in range(g.start[v], g.start[v + 1]):
        to = g.elist[i][0]
        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):
    ids = s.scc_ids()
    group_num = ids[0]
    counts = [0] * group_num
    for x in ids[1]: counts[x] += 1
    groups = [[] for _ in range(group_num)]
    for i in range(s._n):
      groups[ids[1][i]].append(i)
    return groups
 
def nasu(D, XY):
  ts = two_sat(N)
  for i in range(N):
    for j in range(i + 1, N):
      xi, yi = XY[i]
      xj, yj = XY[j]
      # 距離がD未満の組み合わせに関して、
      # 少なくとも一つは使用しない
      # → 少なくとも一つは別の座標を使用する
      # というルールを追加する
      if (abs(xi - xj) < D):
        ts.add_clause(i, False, j, False)
      if (abs(xi - yj) < D):
        ts.add_clause(i, False, j, True)
      if (abs(yi - xj) < D):
        ts.add_clause(i, True, j, False)
      if (abs(yi - yj) < D):
        ts.add_clause(i, True, j, True)
  if ts.satisfiable():
    return True
  return False

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

ok = 0
ng = 10 ** 9 + 1

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

print(ok)