제출 #1310156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310156		forevpurity	XOR (IZhO12_xor)	C++20	100 / 100	117 ms	27128 KiB

xor

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

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

struct Trie {
  struct Node {
    int child[2];
    int mn_idx = 1e9;
    Node() { fill(child, child + 2, -1); }
    int& operator[](int c) { return child[c]; }
  };

  const int LG = 30;
  vector<Node> nodes;

  Trie() { nodes.emplace_back(); }

  void add(int x, int idx) {
    int at = 0;
    for (int i = LG; i >= 0; i--) {
      int c = (x >> i) & 1;
      if (nodes[at][c] == -1) {
        nodes[at][c] = size(nodes);
        nodes.emplace_back();
      }
      at = nodes[at][c];
      nodes[at].mn_idx = min(nodes[at].mn_idx, idx);
    }
  }

  int query(int x, int k) {
    int at = 0;
    int idx = 1e9;
    for (int i = LG; i >= 0; i--) {
      if (at == -1) break;
      int xx = (x >> i) & 1;
      int xk = (k >> i) & 1;
      if (xk == 1) {
        at = nodes[at][xx ^ 1];
      } else {
        if (nodes[at][xx ^ 1] != -1) { idx = min(idx, nodes[nodes[at][xx ^ 1]].mn_idx); }
        at = nodes[at][xx];
      }
    }
    if (at != -1) idx = min(idx, nodes[at].mn_idx);
    return idx;
  }
};

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

  int t = 1;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> vec(n + 1);
    for (int i = 1; i <= n; i++) cin >> vec[i];

    vector<int> pxo(n + 1);
    for (int i = 1; i <= n; i++) pxo[i] ^= (pxo[i - 1] ^ vec[i]);

    Trie tr;
    tr.add(0, 0);
    int blen = 0, br;
    for (int i = 1; i <= n; i++) {
      tr.add(pxo[i], i);
      int idx = tr.query(pxo[i], k);
      if (idx == 1e9) continue;
      if (i - idx > blen) blen = i - idx, br = i;
    }
    int bl = br - blen + 1;
    cout << bl << " " << blen << '\n';
  }

  return 0;
}

• Subtask 1: 100 / 100