Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define F first
- #define S second
- #define pb push_back
- #define mp make_pair
- #define eb emplace_back
- int rnd() {
- return (rand() << 16) ^ rand();
- }
- const int N = 200100;
- const int M = 63;
- pair<int,int> dp[M][N][2];
- int cnt[M];
- #define FILE "xor-cypher"
- int main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- freopen(FILE".in", "r", stdin);
- freopen(FILE".out", "w", stdout);
- #endif
- for (int i = 0; i < M; i++){
- for (int j = 0; j < N; j++){
- for (int q = 0; q < 2; q++){
- dp[i][j][q] = {3, 1e9};
- }
- }
- }
- int n;
- cin >> n;
- long long S;
- cin >> S;
- for (int i = 0; i < n; i++){
- long long x;
- cin >> x;
- for (int j = 0; j < M; j++){
- cnt[j] += ((x & (1ll << j)) != 0);
- }
- }
- int kek[M];
- for (int i = 0; i < M; i++){
- kek[i] = ((S & (1ll << i)) != 0);
- }
- dp[0][0][0] = dp[0][0][1] = {0, 0};
- for (int i = 0; i < M - 1; i++){
- for (int j = 0; j < N; j++){
- for (int q = 0; q < 2; q++){
- if (dp[i][j][q].F == 3) continue;
- int cur;
- cur = j + cnt[i];
- if (cur % 2 == kek[i] && (cur >> 1) < N){
- dp[i + 1][cur >> 1][0] = min(dp[i + 1][cur >> 1][0], {q, j});
- }
- cur = j + (n - cnt[i]);
- if (cur % 2 == kek[i] && (cur >> 1) < N){
- dp[i + 1][cur >> 1][1] = min(dp[i + 1][cur >> 1][1], {q, j});
- }
- }
- }
- }
- pair<int,int> y = {3, -1};
- for (int q = 1; q >= 0; q--){
- if (dp[M - 1][0][q].F != 3){
- y = dp[M - 1][0][q];
- }
- }
- if (y.F == 3){
- cout << -1 << endl;
- return 0;
- }
- long long ans = 0;
- for (int i = M - 1; i > 0; i--){
- if (y.F) ans += (1ll << (i - 1));
- y = dp[i][y.S][y.F];
- }
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement