Submission #1036956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036956		pera	XOR (IZhO12_xor)	C++17	0 / 100	123 ms	262144 KiB

xor

#include<bits/stdc++.h>
using namespace std;
const int N = 250000 + 1 , LOG = 31;
int n , x , id = 0;
vector<int> a(N) , mx(N * LOG);
vector<vector<int>> t(N * LOG , vector<int>(2));
void UPD(int e , int o){
   int v = 0;
   for(int bit = LOG - 1;bit >= 0;bit --){
      if(!t[v][e >> bit & 1]){
         t[v][e >> bit & 1] = ++id;
         mx[v] = o;
      }
      v = t[v][e >> bit & 1];
   }
}
int GET(int e){
   int v = 0 , r = 0 , s = 0;
   for(int bit = LOG - 1;bit >= 0;bit --){
      int _e = e >> bit & 1;
      int _x = x >> bit & 1;
      if(!_x){
         r = max(r , mx[t[v][!_e]]);
         v = t[v][_e];
         if(!v){
            return r;
         }
         continue;
      }
      v = t[v][_e ^ 1];
      s ^= (1 << bit);
      if(!v){
         return r;
      }
   }
   return max(r , mx[v]);
}
int main(){
   cin >> n >> x;
   for(int i = 1;i <= n;i ++){
      cin >> a[i];
      a[i] ^= a[i - 1];
   }
   int L = -1 , sz = -1;
   for(int l = n;l >= 0;l --){
      int r = GET(a[l]);
      if(l < r && r <= n && (a[r] ^ a[l]) >= x && r - l >= sz){
         L = l + 1;
         sz = r - l;
      }
      UPD(a[l] , l);
   }
   cout << L << " " << sz << endl;
}

• Subtask 1: 0 / 100