제출 #998975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
998975		nguyennh	XOR (IZhO12_xor)	C++14	0 / 100	18 ms	2648 KiB

xor

#include<bits/stdc++.h>
#define el '\n'
using namespace std;

const int MN = 1e5 + 5;
const int N = 3e5 + 5;
const int LG = 31;

int a[N];

struct Trie{
  struct Node{
    int child[2] , min_pos;
  } node[MN];
  
  int cur;
  Trie () : cur(0){
    memset(node[0].child , -1 , sizeof(node[cur].child));
    node[0].min_pos = INT_MAX;
  }
  
  int new_node(){
    cur++;
    memset(node[cur].child , -1 , sizeof(node[cur].child));
    node[cur].min_pos = INT_MAX;
    return cur;
  }
  
  void add(int x , int pos){
    int root = 0;
    for ( int i = LG ; i >= 0 ; i-- ){
      int c = x >> i & 1;
      if (node[root].child[c] == -1) node[root].child[c] = new_node();
      root = node[root].child[c];
      node[root].min_pos = min(node[root].min_pos , pos);
    }
  }
  
  int query(int x , int k){
    int root = 0 , ans = INT_MAX;
    for ( int i = LG ; i >= 0 ; i-- ){
      int bitx = x >> i & 1;
      int bitk = k >> i & 1;
      if (!bitk){
        if (node[root].child[bitx ^ 1] != -1){
          int new_root = node[root].child[bitx ^ 1];
          ans = min(ans , node[new_root].min_pos);
        }
        if (node[root].child[bitx] == -1) return ans;
        root = node[root].child[bitx];
      }
      else {
        if (node[root].child[bitx ^ 1] == -1) return ans;
        root = node[root].child[bitx ^ 1];
      }
    }
    ans = min(ans , node[root].min_pos);
    return ans;
  }
};

int32_t main (){
//  freopen("dmm.inp" , "r" , stdin);
//  freopen("dmm.out" , "w" , stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n , k;
  cin >> n >> k;
  for ( int i = 1 ; i <= n ; i++ ) cin >> a[i];
  vector<int64_t> pref(n + 5);
  for ( int i = 1 ; i <= n ; i++ ) pref[i] = pref[i - 1] ^ a[i];
  Trie tr;
  int ans = 0 , pos = INT_MAX;
  for ( int i = 1 ; i <= n ; i++ ){
    tr.add(pref[i - 1] , i - 1);
    int left_bound = tr.query(pref[i] , k);
    if (left_bound == INT_MAX) continue;
    if (ans < i - left_bound){
      ans = i - left_bound;
      pos = left_bound + 1;
    }
    else if (ans == i - left_bound){
      pos = min(pos , left_bound + 1);
    }
  }
  cout << (pos == INT_MAX ? 0 : pos) << " " << ans;
}

• Subtask 1: 0 / 100