結果
問題 |
No.2024 Xer
|
ユーザー |
|
提出日時 | 2022-07-29 23:26:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 228 ms / 2,000 ms |
コード長 | 3,112 bytes |
コンパイル時間 | 1,596 ms |
コンパイル使用メモリ | 182,696 KB |
実行使用メモリ | 26,624 KB |
最終ジャッジ日時 | 2024-07-19 16:59:44 |
合計ジャッジ時間 | 5,585 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 47 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; #define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i) #define rep(i, n) drep(i, 0, n - 1) #define all(a) (a).begin(), (a).end() #define pb push_back #define fi first #define se second const ll MOD = 1000000007; const ll MOD2 = 998244353; const ll INF = 1LL << 60; const ll N_MAX = 2e5; int main(){ ll n, x; cin >> n >> x; vector<ll> a(n); rep(i, n) cin >> a[i]; ll md = 30; if(x == 0) md = 0; else{ while (!((x >> md) & 1)) md--; } map<ll, vector<ll>> mp; rep(i, n){ mp[a[i]>>(md+1)].pb(a[i]); } for(auto itr=mp.begin(); itr!=mp.end(); itr++){ vector<ll> zero; vector<ll> one; for(ll i : mp[(*itr).fi]){ if((i>>md) & 1) one.pb(i); else zero.pb(i); } sort(all(zero)); sort(all(one)); ll nz = (ll)zero.size(); ll no = (ll)one.size(); if(abs(nz-no) >= 2){ cout << "No" << endl; return 0; } rep(i, nz-1){ if(zero[i] == zero[i+1]){ cout << "No" << endl; return 0; } } rep(i, no-1){ if(one[i] == one[i+1]){ cout << "No" << endl; return 0; } } if((nz==0 && no==1) || (nz==1 && no==0)) continue; bool flag1 = false; bool flag2 = false; if(nz == no){ // 0, 1, 0, 1 flag1 = true; for(ll i=0; i<nz; i++){ if(!(zero[i] < (ll)(one[i] ^ x) && (ll)(zero[i] ^ x) < one[i])){ flag1 = false; } } // 1, 0, 1, 0 flag2 = true; for(ll i=0; i<nz; i++){ if(!(one[i] < (ll)(zero[i] ^ x) && (ll)(one[i] ^ x) < zero[i])){ flag2 = false; } } if(!flag1 && !flag2){ cout << "No" << endl; return 0; } }else if(nz < no){ flag1 = true; for(ll i=0; i<nz; i++){ if(!(one[i] < (ll)(zero[i] ^ x) && (ll)(one[i] ^ x) < zero[i])){ flag2 = false; } } if(!(zero[nz-1] < (ll)(one[no-1] ^ x) && (ll)(zero[nz-1] ^ x) < one[no-1])){ flag1 = false; } if(!flag1){ cout << "No" << endl; return 0; } }else if(no < nz){ flag1 = true; for(ll i=0; i<no; i++){ if(!(zero[i] < (ll)(one[i] ^ x) && (ll)(zero[i] ^ x) < one[i])){ flag2 = false; } } if(!(one[no-1] < (ll)(zero[nz-1] ^ x) && (ll)(one[no-1] ^ x) < zero[nz-1])){ flag1 = false; } if(!flag1){ cout << "No" << endl; return 0; } } } cout << "Yes" << endl; }