Editorial for XOR-Gun

Notice that if we can erase the sequence using more than 22 operations then we can also erase it using 2\le 2 operations. Why? That’s because xxx=xx \oplus x \oplus x = x. So we just have to check if the sequence can be erased using 11 or 22 operations.

If the XOR of elements of the whole sequence is xx, then we can erase it using 11 operations.

We can erase the sequence using exactly 22 operations iff -

  • a1a2an=0a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0

  • There exists a non-empty subset of aa such that the XOR of the elements of that subsequence is xx.

We can check the second condition in O(log(230))\mathcal{O}(\log(2^{30})) using the basis vectors of the elements of aa and checking if xx is in the same subspace. Check this to know more.

So the problem can be solved in O(q30)\mathcal{O}(q \cdot 30).

Code(C++):

#include<bits/stdc++.h>
using namespace std;

struct Basis {
  vector<int> a;
  void insert(int x) {
    for (auto &i: a) x = min(x, x ^ i);
    if (!x) return;
    for (auto &i: a) if ((i ^ x) < i) i ^= x;
    a.push_back(x);
    sort(a.begin(), a.end());
  }
  bool can(int x) {
    for (auto &i: a) x = min(x, x ^ i);
    return !x;
  }
}t;
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q; cin >> n >> q;
  int tot = 0;
  for (int i = 1; i <= n; i++) {
    int x; cin >> x;
    tot ^= x;
    t.insert(x);
  }
  while (q--) {
    int x; cin >> x;
    if (tot == x) {
      cout << 1 << '\n';
    }
    else if (tot == 0 and t.can(x)) {
      cout << 2 << '\n';
    }
    else {
      cout << -1 << '\n';
    }
  }
  return 0;
}

Statistics


75% Solution Ratio

NirjhorEarliest, 5M ago

LUMBERJACK_MANFastest, 0.1s

prodip_bsmrstuLightest, 1.0 MB

serotoninShortest, 571B

Toph uses cookies. By continuing you agree to our Cookie Policy.