Submission #41979922

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
#define int ll

const int MAXN = 1e5+10,MAXM = 6e6+10;

int n,a[MAXN*2];

int ch[MAXM][2],cnt[MAXM],tot;

void ins(int u,int val,int k){
	cnt[u]++;
	if(k==-1)return;

	int v = val>>k&1;
	if(!ch[u][v])ch[u][v] = ++tot;
	ins(ch[u][v],val,k-1);
}

int lim;

int dp(int,int);

int V(int x,int y,int k){
	if(!x && !y)return 0;
	if(cnt[x] > cnt[y])swap(x,y);

	int num = dp(y,k-1);
	return cnt[x] + min(num,(cnt[y]-cnt[x])/2);
}

int g(int x,int y,int k){
	if(!x || !y)return 0;
	if(k==-1){
		return min(cnt[x],cnt[y]);
	}
	if(lim>>k&1){
		return g(ch[x][0],ch[y][1],k-1) + g(ch[x][1],ch[y][0],k-1);
	}else{
		int a = ch[x][0],b = ch[x][1],c = ch[y][0],d = ch[y][1];
		int ret = min(cnt[a],cnt[d]) + min(cnt[b],cnt[c]);
		
		if(cnt[a]>cnt[d] && cnt[c]>cnt[b]){
			int num = g(a,c,k-1);
			num = min(num,min(cnt[a]-cnt[d],cnt[c]-cnt[b]));
			ret += num;
		}
		if(cnt[a]<cnt[d] && cnt[c]<cnt[b]){
			int num = g(b,d,k-1);
			num = min(num,min(cnt[d]-cnt[a],cnt[b]-cnt[c]));
			ret += num;
		}
		
		return ret;
	}
}

int dp(int u,int k){
	if(!u)return 0;

	if(k==-1){
		return cnt[u]/2;
	}

	if(lim>>k&1){ 
		return g(ch[u][0],ch[u][1],k-1);
	}else{ 
		return V(ch[u][0],ch[u][1],k);
	}
}

const int VV = 29;

int chk(int mid){
	lim = mid;

	int ret = dp(1,VV);

	return ret >= (n+1)/2;
}

signed main(){
	cin>>n;

	tot = 1;
	rep(i,1,2*n)cin>>a[i],ins(1,a[i],VV);

	int L = 1,R = (1<<30)-1,ret = 0;

	while(L<=R){
		int mid = (L+R)>>1;

		if(chk(mid)){
			ret = mid; L = mid+1;
		}else{
			R = mid-1;
		}
	}
	cout<<ret<<"\n";

    return 0;
}

Submission Info

Judge Result