제출 #1329824

#제출 시각아이디문제언어결과실행 시간메모리
1329824twmnh195XOR (IZhO12_xor)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(a) (a).begin(), (a).end()
#define el '\n'
#define sz(a) (int)(a).size()

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) 0
#define debug_itr(...) 0
#define debug_bits(...) 0
#endif

// الحمد لله رب العالمين

int k;
const int B = 2;

struct node {
  int adj[2]{};
  int pre = 0, mnidx = 1e7;
  int &operator[](char x) { return adj[x]; }
};

struct Trie {
  vector<node> trie;
  int newnode() {
    trie.emplace_back();
    return trie.size() - 1; // node index in trie vector
  }
  Trie() {
    trie.clear();
    newnode();
  }
  void insert(int x, int j) {
    int u = 0;
    for (int i = B; i >= 0; --i) {
      int b = x >> i & 1;
      if (!trie[u][b]) {
        trie[u][b] = newnode();
      }
      trie[u].mnidx = min(trie[u].mnidx, j);
      u = trie[u][b];
      trie[u].pre++;
      trie[u].mnidx = min(trie[u].mnidx, j);
      debug(u, trie[u].mnidx);
    }
  }
  int query(int x) {
    int ans = 1e7, u = 0, i = B;
    debug(x);
    for (; i >= 0; --i) {
      int b = x >> i & 1, bk = k >> i & 1;
      if (!bk) {
        if (trie[u][b ^ 1]) {
          ans = min(ans, trie[u].mnidx);
          debug(b, bk, u, ans);
        }
        if (trie[u][b])
          u = trie[u][b];
        else
          break;
      } else {
        if (trie[u][b ^ 1]) {
          u = trie[u][b ^ 1];
        } else
          break;
      }
    }
    if (i == -1) {
      ans = min(ans, trie[u].mnidx);
      debug(u, ans);
    }
    return ans;
  }
};

void solve() {
  int n;
  cin >> n >> k;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; ++i)
    cin >> a[i];
  Trie t;
  t.insert(0, 0);
  int idx, len = 0, ans;
  for (int i = 1; i <= n; ++i) {
    a[i] ^= a[i - 1];
    t.insert(a[i], i);
    idx = t.query(a[i]);
    if (i - idx > len)
      len = i - idx, ans = idx + 1;
  }
  cout << ans << ' ' << len << el;
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  int t = 1;
  // cin >> t;
  while (t--)
    solve();
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...