結果

問題 No.130 XOR Minimax
コンテスト
ユーザー vjudge1
提出日時 2025-11-08 16:56:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,036 bytes
コンパイル時間 1,388 ms
コンパイル使用メモリ 162,328 KB
実行使用メモリ 28,492 KB
最終ジャッジ日時 2025-11-08 16:59:20
合計ジャッジ時間 5,914 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 WA * 6 RE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int sum=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
const int N=1e5+5;
int cnt,n;
int num[N];
int s[N],a[N];
int nxt[N][26*2+10];
void add(){
	int now=0,len=30;
	for(int i=0;i<len;i++){
		int v=s[i];
		if(!nxt[now][v]) nxt[now][v]=++cnt;
		now=nxt[now][v];
		num[now]++;
	}
}
void query(){
	int now=0,len=30,x=0,ans=0;
	for(int i=0;i<len;i++){
		if(!nxt[now][1]){
			s[i]=0;
			now=nxt[now][0];
			continue;
		}
		int n1=nxt[now][1],n2=nxt[now][0];
		if(i==1&&num[n1]==n||num[n1]==num[now]){
			s[i]=1;
			now=n1;
		}
		else{
			s[i]=0;
			now=n2;	
		}
	}
	for(int i=0;i<len;i++){
		//cout<<s[i];
		if(s[i]) x+=(1<<(29-i));
	}
//	cout<<x<<endl;
	for(int i=1;i<=n;i++){
		ans=max(ans,a[i]^x);
	}
	cout<<ans<<endl;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		for(int j=0;j<30;j++){
			s[j]=(bool)(a[i]&(1<<(29-j)));
		}
		add();
	}
	query();
	return 0;
}
0