Submission #571430

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
571430	2022-06-02T08:03:16 Z	Shin	XOR (IZhO12_xor)	C++14	100 / 100	157 ms	59360 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	592 KB	Output is correct
5	Correct	6 ms	1876 KB	Output is correct
6	Correct	7 ms	2084 KB	Output is correct
7	Correct	8 ms	2132 KB	Output is correct
8	Correct	8 ms	2184 KB	Output is correct
9	Correct	59 ms	27832 KB	Output is correct
10	Correct	61 ms	27980 KB	Output is correct
11	Correct	63 ms	27852 KB	Output is correct
12	Correct	58 ms	27920 KB	Output is correct
13	Correct	59 ms	27972 KB	Output is correct
14	Correct	59 ms	28020 KB	Output is correct
15	Correct	59 ms	27996 KB	Output is correct
16	Correct	60 ms	27900 KB	Output is correct
17	Correct	153 ms	59340 KB	Output is correct
18	Correct	152 ms	59324 KB	Output is correct
19	Correct	150 ms	59360 KB	Output is correct
20	Correct	157 ms	59352 KB	Output is correct