Submission #992987

#	Time	Username	Problem	Language	Result	Execution time	Memory
992987		tch1cherin	XOR (IZhO12_xor)	C++17	100 / 100	82 ms	30388 KiB

xor

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

const int BIT_LEN = 30;

struct trie {
  struct node {
    array<int, 2> go = {0, 0};
    int min_x = numeric_limits<int>::max();
  };

  vector<node> T = {node()};

  void insert(int value, int x) {
    int v = 0;
    for (int i = BIT_LEN - 1; i >= 0; i--) {
      int bit = (value >> i) & 1;
      if (!T[v].go[bit]) {
        T[v].go[bit] = (int)T.size();
        T.push_back(node());
      }
      v = T[v].go[bit];
      T[v].min_x = min(T[v].min_x, x);
    }
  }

  int min_query(int xor_val, int lb) {
    int answer = numeric_limits<int>::max();
    int v = 0;
    for (int i = BIT_LEN - 1; i >= 0; i--) {
      int bit_xor = (xor_val >> i) & 1;
      int bit_lb = (lb >> i) & 1;
      if (bit_lb == 0) {
        answer = min(answer, T[T[v].go[bit_lb ^ bit_xor ^ 1]].min_x);
      }
      v = T[v].go[bit_lb ^ bit_xor];
      if (!v) {
        break;
      }
    }
    answer = min(answer, T[v].min_x);
    return answer;
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, x;
  cin >> N >> x;
  vector<int> a(N);
  for (int &value : a) {
    cin >> value;
  }
  vector<int> pref(N + 1);
  for (int i = 0; i < N; i++) {
    pref[i + 1] = pref[i] ^ a[i];
  }
  trie T;
  T.insert(0, 0);
  pair<int, int> answer = {0, 0};
  for (int i = 1; i <= N; i++) {
    int min_x = T.min_query(pref[i], x);
    if (min_x < i) {
      answer = max(answer, {i - min_x, -min_x});
    }
    T.insert(pref[i], i);
  }
  cout << -answer.second + 1 << " " << answer.first << "\n";
}

• Subtask 1: 100 / 100