Submission #1353490

#TimeUsernameProblemLanguageResultExecution timeMemory
1353490vjudge1XOR (IZhO12_xor)C++17
100 / 100
68 ms21520 KiB
#include <bits/stdc++.h>
#define el cout << '\n'
#define fi first
#define se second
#define ll long long
#define pb push_back
#define num(_a) (_a-'0')
#define pii pair<int,int>
#define pli pair<ll, int>
#define pil pair<int,ll>
using namespace std;
template <typename T>
void debug_out(const T& value) {
    cerr << value << endl;
}
template <typename T, typename... Args>
void debug_out(const T& first, const Args&... args) {
    cerr << first << ", ";
    debug_out(args...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
const int mod = (int)1e9 + 7;
template<class T> bool minimize(T& cur, const T& val) { return val < cur ? cur = val, 1 : 0; }
template<class T> bool maximize(T& cur, const T& val) { return val > cur ? cur = val, 1 : 0; }
using namespace std;
const ll infl = 1e18;
const int inft = 1e9;
const int maxn = (long long)250000;

int ch[(maxn + 1) * 30 + 4][2];
int mnid[(maxn + 1) * 30 + 4];
int tot = 1;
int x;
void newnode(int id){
  ch[id][0] = ch[id][1] = 0;
  mnid[id] = inft;
}
void add(int val, int id){
  int u = 1;
  mnid[u] = min(mnid[u], id);
  for(int b = 29; b >= 0; b--){
    int bit = (val >> b) & 1;
    if(!ch[u][bit]){
        ++tot;
        newnode(tot);
        ch[u][bit] = tot;
    }
    u = ch[u][bit];
    mnid[u] = min(mnid[u], id);
  }
}
int querymin(int val){
   int u = 1;
   int ans = inft;
   for(int b = 29; b >= 0; b--){
    int vb = (val >> b) & 1;
    int xb = (x >> b) & 1;
    if(xb == 0){
        int g = ch[u][vb ^ 1];
        if(g) ans = min(ans, mnid[g]);
        u = ch[u][vb];
    } else u = ch[u][vb ^ 1];
   }
   if(u) ans = min(ans, mnid[u]);
   return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
     int n;
    cin >> n >> x;
    newnode(1);
    int pref = 0;
    int ress = 1;
    int resl = 0;
    add(0, 0);
    for(int r = 1; r <= n; r++){
        int a;
        cin >> a;
        pref ^= a;
        int t = querymin(pref);
        if(t != inft){
            int len = r - t;
            int s = t + 1;
            if(len > resl || (len == resl && s < ress)){
                resl = len;
                ress = s;
            }
        }
        add(pref, r);
    }

    cout << ress << " " << resl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...