#415674 (C++14) No.130 XOR Minimax

• 問題: No.130 XOR Minimax
• ユーザー: 👑 CleyL
• 提出日時: 2020-01-11 01:48:55
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 2,433 bytes
• コンパイル時間: 879 ms
• コンパイル使用メモリ: 97,916 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-23 22:25:32
• 合計ジャッジ時間: 2,180 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	15 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	12 ms; 5,248 KB
testcase_05	AC	18 ms; 5,248 KB
testcase_06	AC	15 ms; 5,248 KB
testcase_07	WA	-
testcase_08	AC	23 ms; 5,248 KB
testcase_09	WA	-
testcase_10	AC	7 ms; 5,248 KB
testcase_11	AC	20 ms; 5,248 KB
testcase_12	AC	4 ms; 5,248 KB
testcase_13	AC	17 ms; 5,248 KB
testcase_14	AC	27 ms; 5,248 KB
testcase_15	WA	-
testcase_16	AC	19 ms; 5,248 KB
testcase_17	AC	20 ms; 5,248 KB
testcase_18	AC	22 ms; 5,248 KB
testcase_19	AC	26 ms; 5,248 KB
testcase_20	AC	13 ms; 5,248 KB
testcase_21	WA	-
testcase_22	AC	7 ms; 5,248 KB
testcase_23	WA	-

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:101:17: warning: left shift count >= width of type [-Wshift-count-overflow]
  101 |   b.push_back((2<<50));
      |                ~^~~~

ソースコード

//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;

#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)


#define MAX 1000000000
#define MOD 1000000007
#define EPS (1e-10)

#define pb push_back
#define fir first
#define scn second
#define ednl endl

#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")



/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
vector.unique()は隣接した同じ要素を削除するので先にソートをする

計算量は変わらないが楽できるシリーズ
C++11以降でmin({a,b,c...})で複数個のmic,maxを処理できる
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる

*/
template <typename T>
T gcd(T a,T b){
  if(a%b==0)return b;
  else return gcd(b,a%b);
}
template <typename T>
T lcm(T a,T b){
  return a/gcd(a,b)*b;
}
__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);
  //cout << beg << " " << b[en] << " " << k << endl;
  if(x == b.begin()+beg && k != b[en]){
    if(k%2)return ans;
    return dfs(beg,en,k+(km/2),km/2,ans);
  }else if(x == b.begin()+en && k != b[en]){
    if(k%2)return ans;
    return dfs(beg,en,k-(km/2),km/2,ans);
  }else{
    //cout << "!!" <<ans << " " << km << endl;
    ans += km;
    
    if(k%2)return ans;
    return min(dfs(x-b.begin(),en,k+(km/2),km/2,ans),dfs(beg,x-b.begin()-1,k-(km/2),km/2,ans));
  }
}
int main() { 
  int n;cin>>n;
  int a[n];
  for(int i = 0; n > i; i++){
    cin>>a[i];
    b.push_back(a[i]);
    int nw = 0;
  }
  sort(b.begin(),b.end());
  b.push_back((2<<50));
  ll k = (2<<29);
  int beg = 0;
  int en = n;
  int ans = 0;
  cout << dfs(beg,en,k,k,0) << endl;

}