結果
問題 | No.130 XOR Minimax |
ユーザー |
👑 |
提出日時 | 2020-02-25 03:39:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 25 ms / 5,000 ms |
コード長 | 1,312 bytes |
コンパイル時間 | 929 ms |
コンパイル使用メモリ | 99,720 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-12 22:55:31 |
合計ジャッジ時間 | 2,130 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
//author:luckYrat(twitter:@luckYrat_) //#include <bits/stdc++.h> //def #include <iostream> #include <cmath> #include <algorithm> #include <iomanip> //array #include <vector> #include <set> #include <stack> #include <queue> #include <map> #include <utility> #include <climits> using namespace std; typedef pair<int,int> P; typedef long long ll; __attribute__((constructor)) void initial() { cin.tie(0); ios::sync_with_stdio(false); } vector<ll> b; int dfs(int beg,int en,ll k,ll km,int ans){ auto x = lower_bound(b.begin()+beg,b.begin()+en,k)-b.begin(); //cout << beg << " " << en << " " << x << " " << k << endl; if(x == beg){ if(k%2)return ans; //cout << beg << " " << en << endl; return dfs(beg,en,k+(km/2),km/2,ans); }else if(x == en && k > b[en]){ if(k%2)return ans; //cout << beg << " " << en << endl; return dfs(beg,en,k-(km/2),km/2,ans); }else{ ans += km; if(k%2)return ans; //cout << x << " " << en << ":" << beg << " " << x-1<< endl; return min(dfs(x,en,k+(km/2),km/2,ans),dfs(beg,x-1,k-(km/2),km/2,ans)); } } int main() { int n;cin>>n; ll a[n]; for(int i = 0; n > i; i++){ cin>>a[i]; b.push_back(a[i]); } sort(b.begin(),b.end()); //b.push_back((2LL<<30LL)); cout << dfs(0,n-1,(2LL<<29LL),(2LL<<29LL),0) << endl; }