Submission #1256820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256820		greenbinjack	XOR (IZhO12_xor)	C++20	100 / 100	91 ms	94284 KiB

xor

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
using LL = long long;

#define all(V) V.begin(), V.end()
 
template <typename DT> using ordered_set = tree <DT, null_type, less <DT>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename DT> using minheap = priority_queue < DT, vector <DT>, greater <DT> >;
template <class T> bool chMax (T &x, T y) { return y > x ? x = y, 1 : 0; }
template <class T> bool chMin (T &x, T y) { return y < x ? x = y, 1 : 0; }

const int B = 30;
const int MAX_NODES = (32 * 250000) + 69;
int nxt[MAX_NODES][2], sz[MAX_NODES], node_count = 0;

void insert(int val, int idx) {
  int cur = 0;
  for (int bit = B - 1; bit >= 0; bit--) {
    int b = (val >> bit) & 1;
    if (nxt[cur][b] == -1) {
      nxt[cur][b] = ++node_count;
    }
    cur = nxt[cur][b];
    sz[cur] = min (sz[cur], idx);
  }
}

int query(int x, int k) {
  int cur = 0, ans = INT_MAX;
  for (int bit = B - 1; bit >= 0; bit--) {
    if (cur == -1) break;
    int xb = (x >> bit) & 1;
    int kb = (k >> bit) & 1;
    if (not kb) {
      if (nxt[cur][xb ^ 1] != -1) ans = min (ans, sz[nxt[cur][xb ^ 1]]);
      cur = nxt[cur][xb];
    } else {
      cur = nxt[cur][xb ^ 1];
    }
  }
  if (cur != -1) {
    ans = min (ans, sz[cur]);
  }
  return ans;
}

int main() {
  cin.tie(nullptr)->ios_base ::sync_with_stdio(false);

  int n, k;
  cin >> n >> k;

  memset(nxt, -1, sizeof(nxt));  
  fill (sz, sz + MAX_NODES, INT_MAX);
  int pref = 0;
  insert(pref, 0);

  int ans = 0, ans_id = -1;
  for (int i = 1, x; i <= n; i++) {
    cin >> x;
    pref ^= x;
    int idx = query (pref, k);
    if (idx != INT_MAX) {
      if (i - idx > ans) ans = i - idx, ans_id = idx;
      else if (i - idx == ans) ans_id = min (ans_id, idx);
    }
    insert(pref, i);
  }

  cout << ++ans_id << ' ' << ans << '\n';

  return 0;
}

• Subtask 1: 100 / 100