Submission #1359006

#TimeUsernameProblemLanguageResultExecution timeMemory
1359006bakhtiyarnXOR (IZhO12_xor)C++20
0 / 100
1 ms2628 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 3e5+5;
int a[N];
int l[N*32], r[N*32];
int cnt[N*32];
int n, k;

int idx = 1;

void add(int i, int x){
  int you = 0;
  for(int b=30; b>=0; b--){
    bool is = (1ll<<b)&x;
    if(!is){
      if(!l[you]) l[you] = idx++;
      you = l[you];
    } else {
      if(!r[you]) r[you] = idx++;
      you = r[you];
    }
    
    cnt[you] = min(cnt[you], i);
  }
}

int calc(int you, int x, int b, bool fir){
  if (you == 0 and !fir) return 1e18;
  if(b < 0) return 1e18;

  
  bool is1 = (1ll<<b)&x;
  bool is2 = (1ll<<b)&k;
  
  if(is1){
    if(is2) return calc(l[you], x, b-1, false);
    return min(cnt[l[you]], calc(r[you], x, b-1, false));
} else {
    if(is2) return calc(r[you], x, b-1, false);
    return min(cnt[r[you]], calc(l[you], x, b-1, false));
}
}

void solve(){
  cin >> n >> k;
  for(int i=1; i<=n; i++) cin >> a[i], a[i] ^= a[i-1];
  
  for(int i=0; i<N; i++) cnt[i] = 1e18;

  add(0, 0);
  
  array<int, 2> ans = {1, 1};
  for(int i=1; i<=n; i++) {
    add(i, a[i]);
    int l = calc(0, a[i], 30, true);

    ans = max(ans, {i-l, (-l-1)});
  }
  cout << -ans[1] << " " << ans[0] << '\n';
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  solve();
}
#Result Execution timeMemoryGrader output
Fetching results...