結果

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

ソースコード

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=5e6+5;
const int M=31;
int cnt,n;
int num[N];
int s[M],a[N];
int nxt[N][26*2+10];
void add(){
	int now=0,len=M;
	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=M,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<M;i++){
	//	cout<<s[i];
		if(s[i]) x+=(1<<(M-1-i));
	}
//	cout<<x<<endl;
	for(int i=1;i<=n;i++){
		ans=max(ans,a[i]^x);
	}
	cout<<ans<<endl;
}
signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		for(int j=0;j<M;j++){
		//	cout<<s[j];
			s[j]=(bool)(a[i]&(1<<(M-1-j)));
		}//cout<<endl;
		add();
	}
	query();
	return 0;
}
0