Submission #869117

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869117	2023-11-03T08:52:40 Z	tvladm2009	XOR (IZhO12_xor)	C++17	100 / 100	77 ms	46768 KB

xor

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 250000 + 7;
int trie[30 * N][2], c[30 * N], a[N];
int n, y, id = 0;

void add(int x, int p) {
  int node = 0;
  for (int b = 29; b >= 0; b--) {
    int k = ((x & (1 << b)) > 0);
    if (trie[node][k] == 0) {
      trie[node][k] = ++id;
    }
    node = trie[node][k];
    c[node] = min(c[node], p);
  }
}

int srch(int x) {
  int res = n + 1, node = 0;
  for (int b = 29; b >= 0; b--) {
    int k = ((x & (1 << b)) > 0);
    if (y & (1 << b)) {
      if (k > 0) {
        if (trie[node][0] == 0) {
          break;
        }
        node = trie[node][0];
      } else {
        if (trie[node][1] == 0) {
          break;
        }
        node = trie[node][1];
      }
    } else {
      if (k > 0) {
        if (trie[node][0] > 0) {
          res = min(res, c[trie[node][0]]);
        }
        node = trie[node][1];
      } else {
        if (trie[node][1] > 0) {
          res = min(res, c[trie[node][1]]);
        }
        node = trie[node][0];
      }
    }
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  // freopen("input", "r", stdin);

  cin >> n >> y;
  y--;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i < 30 * N; i++) {
    c[i] = n + 1;
  }
  add(0, 0);
  int ind = 0, k = 0, xr = 0;
  for (int i = 1; i <= n; i++) {
    xr ^= a[i];
    add(xr, i);
    int rez = srch(xr);
    if (i - rez > k) {
      k = i - rez;
      ind = rez;
    } else if (rez == k) {
      ind = min(ind, rez);
    }
  }
  cout << ind + 1 << " " << k << "\n";
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	31064 KB	Output is correct
2	Correct	6 ms	31064 KB	Output is correct
3	Correct	6 ms	31068 KB	Output is correct
4	Correct	6 ms	31068 KB	Output is correct
5	Correct	10 ms	31324 KB	Output is correct
6	Correct	10 ms	31320 KB	Output is correct
7	Correct	10 ms	31324 KB	Output is correct
8	Correct	11 ms	31456 KB	Output is correct
9	Correct	28 ms	38000 KB	Output is correct
10	Correct	28 ms	37968 KB	Output is correct
11	Correct	27 ms	38344 KB	Output is correct
12	Correct	30 ms	37972 KB	Output is correct
13	Correct	27 ms	37968 KB	Output is correct
14	Correct	27 ms	37976 KB	Output is correct
15	Correct	28 ms	38140 KB	Output is correct
16	Correct	28 ms	37968 KB	Output is correct
17	Correct	77 ms	46620 KB	Output is correct
18	Correct	69 ms	46676 KB	Output is correct
19	Correct	67 ms	46768 KB	Output is correct
20	Correct	69 ms	46700 KB	Output is correct