제출 #1036974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036974		pera	XOR (IZhO12_xor)	C++17	100 / 100	114 ms	94328 KiB

xor

#include<bits/stdc++.h>
using namespace std;
const int N = 250000 + 1 , LOG = 31;
int n , x , id = 0 , a[N] , mx[N * LOG] , t[N * LOG][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[t[v][e >> bit & 1]] = 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){
         if(t[v][!_e]) {
            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];
   }
   for(int i = 0;i < N * LOG;i ++){
      mx[i] = 0;
      for(int j = 0;j < 2;j ++){
         t[i][j] = 0;
      }
   }
   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: 100 / 100