Submission #869117

#	Time	Username	Problem	Language	Result	Execution time	Memory
869117		tvladm2009	XOR (IZhO12_xor)	C++17	100 / 100	77 ms	46768 KiB

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 / 100