Submission #571430

#	Time	Username	Problem	Language	Result	Execution time	Memory
571430		Shin	XOR (IZhO12_xor)	C++14	100 / 100	157 ms	59360 KiB

xor

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

struct trie {
  trie *nxt[2];
  int pos;
  trie() {
    nxt[0] = nxt[1] = nullptr;
    pos = (int) 1e9 + 7;
  } 
};

const int LOG = 30;
const int N = 5e5 + 7;

trie *root = new trie();
int n, X;
int pre[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> X;
  for (int i = 1; i <= n; i ++) { 
    int x; cin >> x;
    pre[i] = pre[i - 1] ^ x;
  } 

  auto add = [&](int x, int p) {
    trie *cur = root;
    for (int i = LOG; i >= 0; i --) {
      int bit = (x >> i) & 1;
      if (cur -> nxt[bit] == nullptr) {
        cur -> nxt[bit] = new trie();
      }
      cur = cur -> nxt[bit];
      minimize(cur -> pos, p);
    }
  };

  auto get = [&](int x) {
    trie *cur = root;
    int res = (int) 1e9 + 7;
    for (int i = LOG; i >= 0; i --) {
      if ((x >> i) & 1) {
        if ((X >> i) & 1) {
          if (cur -> nxt[0] == nullptr) {
            return res;
          }
          cur = cur -> nxt[0];
        } else {
          if (cur -> nxt[0] != nullptr) {
            minimize(res, cur -> nxt[0] -> pos);
          }
          if (cur -> nxt[1] == nullptr) {
            return res;
          }
          cur = cur -> nxt[1];
        }
      } else {
        if ((X >> i) & 1) {
          if (cur -> nxt[1] == nullptr) {
            return res;
          }
          cur = cur -> nxt[1];
        } else {
          if (cur -> nxt[1] != nullptr) {
            minimize(res, cur -> nxt[1] -> pos);
          }
          if (cur -> nxt[0] == nullptr) {
            return res;
          }
          cur = cur -> nxt[0];
        }
      }
    }
    minimize(res, cur -> pos);
    return res;
  };

  add(0, 0);
  int best = 0, res = 0;
  for (int i = 1; i <= n; i ++) {
    int p = get(pre[i]);
    if (p < i && maximize(best, i - p)) {
      res = p + 1;
    }
    add(pre[i], i);
  }
  cout << res << " " << best;
  return 0;
}

• Subtask 1: 100 / 100