Submission #711961

#	Time	Username	Problem	Language	Result	Execution time	Memory
711961		badont	XOR (IZhO12_xor)	C++17	100 / 100	176 ms	62308 KiB

xor

#include<iostream>
#include<vector>
#include<algorithm>
#include<array>
#include<cassert>
using namespace std;
using ll = long long;

struct node {
  int sub = 0;
  array<node*, 2> c;

  node() : sub(0), c({nullptr, nullptr}) {};
};

void solve() {
  ll n, k;
  cin >> n >> k;

  vector<ll> a(n);
  for (auto& u : a)
    cin >> u;

  vector b = a;
  for (int i = 1; i < n; i++) {
    b[i] ^= b[i - 1];
  }

  node* root = new node;
  constexpr int B = 31;

  node* cur = root;
  for (int i = B - 1; i >= 0; i--) {
    cur->c[0] = new node;
    cur = cur->c[0];
  }  

  auto add_word = [&](ll x, ll z) {
    node* cur = root;
    for (int i = B - 1; i >= 0; i--) {  
      int b = (x >> i) & 1;
      if (cur->c[b] == nullptr) {
        cur->c[b] = new node;
        cur->c[b]->sub = z; 
        #ifdef LOCAL
        cout << cur->c[b] << " " << x << " " << b << " " << i << "\n";
        #endif
      }
      cur = cur->c[b];
    }
    assert(cur != nullptr);
    #ifdef LOCAL
    cout << cur << " " << cur->sub << "\n";
    #endif
  };

  auto query = [&](ll x) -> int {
    node* cur = root;
    int ret = n + 69;
    for (int i = B - 1; i >= 0; i--) {
      if (cur == nullptr) break;
      int b = (x >> i) & 1;
      int kb = (k >> i) & 1;
      if (kb) {
        cur = cur->c[b ^ 1];
      } else {
        if (cur->c[b ^ 1] != nullptr)
          ret = min(ret, cur->c[b ^ 1]->sub);        
        cur = cur->c[b];
      }
      #ifdef LOCAL
      #endif
    }
    if (cur != nullptr)
      ret = min(ret, cur->sub);
    return ret;
  }; 

  ll ans = 0, stx = -1;
  for (int i = 1; i <= n; i++) {
    ll u = b[i - 1];
    ll x = query(u);
    #ifdef LOCAL
    #endif
    
    if (i - x > ans) {
      ans = i - x;
      stx = x + 1;
    }

    add_word(u, i);
  }

  assert(stx != -1);

  cout << stx << " " << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  return 0;
}

• Subtask 1: 100 / 100