Submission #999001

#	Time	Username	Problem	Language	Result	Execution time	Memory
999001		nguyennh	XOR (IZhO12_xor)	C++14	100 / 100	126 ms	61500 KiB

xor

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

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

int a[N];

struct Trie{
  struct Node{
    Node* child[2];
    int min_pos;
    Node (){
      for ( int i = 0 ; i <= 1 ; i++ ) child[i] = nullptr;
      min_pos = INT_MAX;
    }
  };
  
  int cur;
  Node* root;
  Trie () : cur(0){
    root = new Node();
  }
  
  void add(int x , int pos){
    Node* p = root;
    for ( int i = LG ; i >= 0 ; i-- ){
      int c = x >> i & 1;
      if (!p -> child[c]) p -> child[c] = new Node();
      p = p -> child[c];
      p -> min_pos = min(p -> min_pos , pos);
    }
  }
  
  int get(int x , int k){
    int ans = INT_MAX;
    Node* p = root;
    for ( int i = LG ; i >= 0 ; i-- ){
      int bitx = x >> i & 1;
      int bitk = k >> i & 1;
      if (bitk){
        if (!p -> child[bitx ^ 1]) return ans;
        p = p -> child[bitx ^ 1];
      }
      else {
        if (p -> child[bitx ^ 1]) ans = min(ans , p -> child[bitx ^ 1] -> min_pos);
        if (!p -> child[bitx]) return ans;
        p = p -> child[bitx];
      }
    }
    ans = min(ans , p -> 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.get(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: 100 / 100