Advertisement
Guest User

Untitled

a guest
Apr 9th, 2017
252
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define F first
  6. #define S second
  7. #define pb push_back
  8. #define mp make_pair
  9. #define eb emplace_back
  10.  
  11. int rnd() {
  12.     return (rand() << 16) ^ rand();
  13. }
  14.  
  15. const int N = 200100;
  16. const int M = 63;
  17.  
  18. pair<int,int> dp[M][N][2];
  19. int cnt[M];
  20.  
  21. #define FILE "xor-cypher"
  22. int main() {
  23. #ifdef LOCAL
  24.     freopen("input.txt", "r", stdin);
  25.     freopen("output.txt", "w", stdout);
  26. #else
  27.     freopen(FILE".in", "r", stdin);
  28.     freopen(FILE".out", "w", stdout);
  29. #endif
  30.     for (int i = 0; i < M; i++){
  31.         for (int j = 0; j < N; j++){
  32.             for (int q = 0; q < 2; q++){
  33.                 dp[i][j][q] = {3, 1e9};
  34.             }
  35.         }
  36.     }
  37.     int n;
  38.     cin >> n;
  39.     long long S;
  40.     cin >> S;
  41.     for (int i = 0; i < n; i++){
  42.         long long x;
  43.         cin >> x;
  44.         for (int j = 0; j < M; j++){
  45.             cnt[j] += ((x & (1ll << j)) != 0);
  46.         }
  47.     }
  48.  
  49.     int kek[M];
  50.     for (int i = 0; i < M; i++){
  51.         kek[i] = ((S & (1ll << i)) != 0);
  52.     }
  53.  
  54.     dp[0][0][0] = dp[0][0][1] = {0, 0};
  55.     for (int i = 0; i < M - 1; i++){
  56.         for (int j = 0; j < N; j++){
  57.             for (int q = 0; q < 2; q++){
  58.                 if (dp[i][j][q].F == 3) continue;
  59.                 int cur;
  60.  
  61.                 cur = j + cnt[i];
  62.                 if (cur % 2 == kek[i] && (cur >> 1) < N){
  63.                     dp[i + 1][cur >> 1][0] = min(dp[i + 1][cur >> 1][0], {q, j});
  64.                 }
  65.  
  66.                 cur = j + (n - cnt[i]);
  67.                 if (cur % 2 == kek[i] && (cur >> 1) < N){
  68.                     dp[i + 1][cur >> 1][1] = min(dp[i + 1][cur >> 1][1], {q, j});
  69.                 }
  70.             }
  71.         }
  72.     }
  73.  
  74.     pair<int,int> y = {3, -1};
  75.     for (int q = 1; q >= 0; q--){
  76.         if (dp[M - 1][0][q].F != 3){
  77.             y = dp[M - 1][0][q];
  78.         }
  79.     }
  80.     if (y.F == 3){
  81.         cout << -1 << endl;
  82.         return 0;
  83.     }
  84.     long long ans = 0;
  85.     for (int i = M - 1; i > 0; i--){
  86.         if (y.F) ans += (1ll << (i - 1));
  87.         y = dp[i][y.S][y.F];
  88.     }
  89.     cout << ans << endl;
  90.     return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement