Submission #1126681

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxN = (1 << 15);

void add(vector< vector<int> >& g, int s, int a, int b, int t=0, int l=0, int r=maxN){
	if(b <= l || r <= a) return;
	if(a <= l && r <= b){
		g[2*(s+maxN-1)].push_back(2*t+1);
		return;
	}
	add(g, s, a, b, 2*t+1, l, (l+r)/2);
	add(g, s, a, b, 2*t+2, (l+r)/2, r);
}

void search(const vector< vector<int> >& g, int pos, int k, vector<int>& key, vector<int>& order, bool first){
	if(key[pos] != -1) return;
	key[pos] = k;
	for(int i=0;i<g[pos].size();i++){
		search(g, g[pos][i], k, key, order, first);
	}
	if(first) order.push_back(pos);
}

bool solve2sat(const vector< vector<int> >& g){
	int n = g.size();
	vector< vector<int> > h(n);
	for(int i=0;i<g.size();++i){
		for(int j=0;j<g[i].size();j++){
			h[g[i][j]].push_back(i);
		}
	}
	vector<int> key(n, -1), order;
	for(int i=0;i<n;i++) search(g, i, i, key, order, true);
	fill(key.begin(), key.end(), -1);
	for(int i=0;i<n;i++) search(h, order[n-1-i], i, key, order, false);
	for(int i=0;i<n;i+=2) if(key[i] == key[i+1]) return false;
	return true;
}

bool check(const vector< pair<int,int> >& vp, const vector< vector<int> >& idx, int thr){
	vector< vector<int> > g(2*(2*maxN-1));
	for(int i=0;i<maxN-1;i++){
		g[2*i+1].push_back(2*(2*i+1)+1);
		g[2*i+1].push_back(2*(2*i+2)+1);
	}
	for(int i=0;i<idx.size();i++){
		int a = idx[i][0]+maxN-1;
		int b = idx[i][1]+maxN-1;
		g[2*a+1].push_back(2*b);
		g[2*b].push_back(2*a+1);
		g[2*a].push_back(2*b+1);
		g[2*b+1].push_back(2*a);
	}
	for(int i=0;i<vp.size();i++){
		int l=-1, r=i;
		while(r-l>1){
			int m = (l+r)/2;
			if(vp[i].first - vp[m].first < thr){
				r = m;
			} else {
				l = m;
			}
		}
		if(0 <= r && r < i) add(g, i, r, i);
		l=i, r=vp.size();
		while(r-l>1){
			int m = (l+r)/2;
			if(vp[m].first - vp[i].first < thr){
				l = m;
			} else {
				r = m;
			}
		}
		if(i < l) add(g, i, i+1, l+1);
	}
	return solve2sat(g);
}

int main(){
	int N;
	while(cin >> N){
		vector< pair<int,int> > vp;
		for(int i=0;i<2*N;i++){
			int x; cin >> x;
			vp.push_back(make_pair(x, i/2));
		}
		sort(vp.begin(), vp.end());
		vector< vector<int> > idx(N);
		for(int i=0;i<vp.size();i++) idx[vp[i].second].push_back(i);
		int L = 0, R = 1000000007;
		while(R - L > 1){
			int mid = (L+R)/2;
			if(check(vp, idx, mid)){
				L = mid;
			} else {
				R = mid;
			}
		}
		cout << L << endl;
	}
}

Submission Info

Judge Result