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:
import sys

class SCC:
  '''
  SCC class with non-recursive DFS.
  '''
  def __init__(self,N):
    self.N = N
    self.G1 = [[] for _ in range(N)]
    self.G2 = [[] for _ in range(N)]
  
  def add_edge(self,a,b):
    self.G1[a].append(b)
    self.G2[b].append(a)
    
  def scc(self):
    self.seen = [0]*self.N
    self.postorder=[-1]*self.N
    self.order = 0
    for i in range(self.N):
      if self.seen[i]:continue
      self._dfs(i)

    self.seen = [0]*self.N
    scclist = []
    for i in self._argsort(self.postorder,reverse=True):
      if self.seen[i]:continue
      cc = self._dfs2(i)
      scclist.append(cc)
    
    return scclist
    
  def _argsort(self,arr,reverse=False):
    shift = self.N.bit_length()+2
    tmp = sorted([arr[i]<<shift | i for i in range(len(arr))],reverse=reverse)
    mask = (1<<shift) - 1
    return [tmp[i] & mask for i in range(len(arr))]
  
  def _dfs(self,v0):
    todo = [~v0, v0]
    while todo:
      v = todo.pop()
      if v >= 0:
        self.seen[v] = 1
        for next_v in self.G1[v]:
          if self.seen[next_v]: continue
          todo.append(~next_v)
          todo.append(next_v)
      else:
        if self.postorder[~v] == -1:
          self.postorder[~v] = self.order
          self.order += 1
    return
  
  def _dfs2(self,v):
    todo = [v]
    self.seen[v] = 1
    cc = [v]
    while todo:
      v = todo.pop()
      for next_v in self.G2[v]:
        if self.seen[next_v]: continue
        self.seen[next_v] = 1
        todo.append(next_v)
        cc.append(next_v)
    return cc

class TwoSAT:
  def __init__(self,N):
    self.N = N
    self.scc = SCC(2*N)
    self.flag=-1
  
  def add_clause(self,i,f,j,g):
    self.scc.add_edge(f*self.N+i,(1^g)*self.N+j)
    self.scc.add_edge(g*self.N+j,(1^f)*self.N+i)
    
  def satisfiable(self):
    if self.flag==-1:
      self.scclist = self.scc.scc()
      self.order = {j:i for i,scc in enumerate(self.scclist) for j in scc}
      self.flag = True
      self.ans = [0]*self.N
      for i in range(self.N):
        if self.order[i] > self.order[self.N+i]:
          self.ans[i] = 1
          continue
        elif self.order[i] == self.order[i+self.N]:
          self.flag = False
          return self.flag
      return self.flag
    else: return self.flag
  
  def answer(self):
    return self.ans
  
def binary_search2(func, left, right):
    while right-left>1:
        middle = (left+right)//2
        y_middle = func(middle)
        if y_middle: left=middle
        else: right=middle
    return left
  
def is_possible(d):
  ts=TwoSAT(N)
  dx,dy = (0,0,1,1),(0,1,0,1)
  _ = [ts.add_clause(i,dx[k],j,dy[k]) for i in range(N-1) for j in range(i+1,N) for k in range(4) if abs(xy[j][dy[k]]-xy[i][dx[k]])<d] 
  return ts.satisfiable()
  
N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]
xymax = max([max(xy[i]) for i in range(N)])
print(binary_search2(is_possible,0,xymax))

Submission status: Time Limit Exceeded

Solution code:
import sys

class SCC:
  '''
  SCC class with non-recursive DFS.
  '''
  def __init__(self,N):
    self.N = N
    self.G1 = [[] for _ in range(N)]
    self.G2 = [[] for _ in range(N)]
  
  def add_edge(self,a,b):
    self.G1[a].append(b)
    self.G2[b].append(a)
    
  def scc(self):
    self.seen = [0]*self.N
    self.postorder=[-1]*self.N
    self.order = 0
    for i in range(self.N):
      if self.seen[i]:continue
      self._dfs(i)

    self.seen = [0]*self.N
    scclist = []
    for i in self._argsort(self.postorder,reverse=True):
      if self.seen[i]:continue
      cc = self._dfs2(i)
      scclist.append(cc)
    
    return scclist
    
  def _argsort(self,arr,reverse=False):
    shift = self.N.bit_length()+2
    tmp = sorted([arr[i]<<shift | i for i in range(len(arr))],reverse=reverse)
    mask = (1<<shift) - 1
    return [tmp[i] & mask for i in range(len(arr))]
  
  def _dfs(self,v0):
    todo = [~v0, v0]
    while todo:
      v = todo.pop()
      if v >= 0:
        self.seen[v] = 1
        for next_v in self.G1[v]:
          if self.seen[next_v]: continue
          todo.append(~next_v)
          todo.append(next_v)
      else:
        if self.postorder[~v] == -1:
          self.postorder[~v] = self.order
          self.order += 1
    return
  
  def _dfs2(self,v):
    todo = [v]
    self.seen[v] = 1
    cc = [v]
    while todo:
      v = todo.pop()
      for next_v in self.G2[v]:
        if self.seen[next_v]: continue
        self.seen[next_v] = 1
        todo.append(next_v)
        cc.append(next_v)
    return cc

class TwoSAT:
  def __init__(self,N):
    self.N = N
    self.scc = SCC(2*N)
    self.flag=-1
  
  def add_clause(self,i,f,j,g):
    self.scc.add_edge(f*self.N+i,(1^g)*self.N+j)
    self.scc.add_edge(g*self.N+j,(1^f)*self.N+i)
    
  def satisfiable(self):
    if self.flag==-1:
      self.scclist = self.scc.scc()
      self.order = {j:i for i,scc in enumerate(self.scclist) for j in scc}
      self.flag = True
      self.ans = [0]*self.N
      for i in range(self.N):
        if self.order[i] > self.order[self.N+i]:
          self.ans[i] = 1
          continue
        elif self.order[i] == self.order[i+self.N]:
          self.flag = False
          return self.flag
      return self.flag
    else: return self.flag
  
  def answer(self):
    return self.ans
  
def binary_search2(func, left, right):
    while right-left>1:
        middle = (left+right)//2
        y_middle = func(middle)
        if y_middle: left=middle
        else: right=middle
    return left
  
def is_possible(d):
  ts=TwoSAT(N)
  for i in range(N-1):
    for j in range(i+1,N):
      for k1,k2 in [(0,0),(0,1),(1,0),(1,1)]:
        pos1,pos2 = xy[i][k1],xy[j][k2]
        if abs(pos2-pos1)<d:
          ts.add_clause(i,k1^1,j,k2^1)
  return ts.satisfiable()
  
N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]
xymax = max([max(xy[i]) for i in range(N)])
print(binary_search2(is_possible,0,xymax))

Submission status: Time Limit Exceeded

Solution code:
import sys

class SCC:
  '''
  SCC class with non-recursive DFS.
  '''
  def __init__(self,N):
    self.N = N
    self.G1 = [[] for _ in range(N)]
    self.G2 = [[] for _ in range(N)]
  
  def add_edge(self,a,b):
    self.G1[a].append(b)
    self.G2[b].append(a)
    
  def scc(self):
    self.seen = [0]*self.N
    self.postorder=[-1]*self.N
    self.order = 0
    for i in range(self.N):
      if self.seen[i]:continue
      self._dfs(i)

    self.seen = [0]*self.N
    scclist = []
    for i in self._argsort(self.postorder,reverse=True):
      if self.seen[i]:continue
      cc = self._dfs2(i)
      scclist.append(cc)
    
    return scclist
    
  def _argsort(self,arr,reverse=False):
    shift = self.N.bit_length()+2
    tmp = sorted([arr[i]<<shift | i for i in range(len(arr))],reverse=reverse)
    mask = (1<<shift) - 1
    return [tmp[i] & mask for i in range(len(arr))]
  
  def _dfs(self,v0):
    todo = [~v0, v0]
    while todo:
      v = todo.pop()
      if v >= 0:
        self.seen[v] = 1
        for next_v in self.G1[v]:
          if self.seen[next_v]: continue
          todo.append(~next_v)
          todo.append(next_v)
      else:
        if self.postorder[~v] == -1:
          self.postorder[~v] = self.order
          self.order += 1
    return
  
  def _dfs2(self,v):
    todo = [v]
    self.seen[v] = 1
    cc = [v]
    while todo:
      v = todo.pop()
      for next_v in self.G2[v]:
        if self.seen[next_v]: continue
        self.seen[next_v] = 1
        todo.append(next_v)
        cc.append(next_v)
    return cc

class TwoSAT:
  def __init__(self,N):
    self.N = N
    self.scc = SCC(2*N)
    self.flag=-1
  
  def add_clause(self,i,f,j,g):
    self.scc.add_edge(f*self.N+i,(1^g)*self.N+j)
    self.scc.add_edge(g*self.N+j,(1^f)*self.N+i)
    
  def satisfiable(self):
    if self.flag==-1:
      self.scclist = self.scc.scc()
      self.order = {j:i for i,scc in enumerate(self.scclist) for j in scc}
      self.flag = True
      self.ans = [0]*self.N
      for i in range(self.N):
        if self.order[i] > self.order[self.N+i]:
          self.ans[i] = 1
          continue
        elif self.order[i] == self.order[i+self.N]:
          self.flag = False
          return self.flag
      return self.flag
    else: return self.flag
  
  def answer(self):
    return self.ans
  
def binary_search2(func, n_min, n_max):
    left,right=n_min,n_max
    y_left, y_right = func(left), func(right)
    while right-left>1:
        middle = (left+right)//2
        y_middle = func(middle)
        if y_left==y_middle: left=middle
        else: right=middle

    return left
  
def is_possible(d):
  ts=TwoSAT(N)
  for i in range(N-1):
    for j in range(i+1,N):
      for k1,k2 in [(0,0),(0,1),(1,0),(1,1)]:
        pos1,pos2 = xy[i][k1],xy[j][k2]
        if abs(pos2-pos1)<d:
          ts.add_clause(i,k1^1,j,k2^1)
  return ts.satisfiable()
  
N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]
print(binary_search2(is_possible,0,10**9))

Submission status: Accepted

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):
        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: Runtime Error

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)
      s = sorted(d.items(), key=cmp_to_key(lambda x, y: x[0] - y[0]),
               reverse=True)
      return list(map(lambda x: [x[0], x[1][0], len(x[1])], s))
     
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: Runtime Error

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)
      s = sorted(d.items(), key=cmp_to_key(lambda x, y: x[0] - y[0]),
               reverse=True)
      return list(map(lambda x: [x[0], x[1][0], len(x[1])], s))
     
    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: Runtime Error

Solution code:
N=int(input())

xy=[[int(i) for i in input().split()] for i in range(N)]
flag=[False for i in range(N)]

z=[[xy[i][0],i] for i in range(N)]
z.extend([[xy[i][1],i] for i in range(N)])
z.sort()

dist=[z[i+1]-z[i] for i in range(2N-1)]
dist.sort()