結果
問題 |
No.130 XOR Minimax
|
ユーザー |
|
提出日時 | 2020-01-11 12:29:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 129 ms / 5,000 ms |
コード長 | 1,045 bytes |
コンパイル時間 | 1,175 ms |
コンパイル使用メモリ | 96,992 KB |
最終ジャッジ日時 | 2025-01-08 17:06:28 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <math.h> using namespace std; typedef long long int ll; int ans=(1<<30); template<int MX,int MXBIT>struct Trie{ int nex[MX][2],sz[MX],num=0; // num is last node in trie Trie(){ for(int i=0;i<MX;i++){ nex[i][0]=nex[i][1]=0; sz[i]=0; } } void ins(ll x,int a=1){ // insert or delete int cur=0; sz[cur]+=a; for(int i=MXBIT-1;i>=0;i--){ int t=(x>>i)&1; if(!nex[cur][t]){ num++; nex[cur][t]=num; } sz[cur=nex[cur][t]]+=a; } } void dfs(int a,int b,int res=0){ if(b==-1){ ans=min(ans,res); return; } if(nex[a][0]&&nex[a][1]){ for(int i=0;i<2;i++){ dfs(nex[a][i],b-1,res^(1<<b)); } } else{ for(int i=0;i<2;i++){ if(nex[a][i]){ dfs(nex[a][i],b-1,res); } } } } }; Trie<(int)1e7,30> T; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector<ll> a(n); for(int i=0;i<n;i++){ cin >> a[i]; T.ins(a[i]); } T.dfs(0,29); cout << ans << endl; }