Submission #1354674

#TimeUsernameProblemLanguageResultExecution timeMemory
1354674vjudge1XOR (IZhO12_xor)C++20
100 / 100
68 ms23396 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 250000 + 5;
const int LOG = 31;
struct Node {
    int child[2];
    int mn;
    Node() {
        child[0]=child[1]=-1;
        mn=INT_MAX;
    }
};
vector<Node> trie;
int new_node(){
    trie.push_back(Node());
    return (int)trie.size() - 1;
}
void insert(int x,int id){
    int cur=0;
    trie[cur].mn=min(trie[cur].mn, id);
    for (int i=LOG;i>=0;i--) {
        int b=(x >> i) & 1;
        if (trie[cur].child[b]==-1)
            trie[cur].child[b]=new_node();
        cur = trie[cur].child[b];
        trie[cur].mn = min(trie[cur].mn, id);
    }
}
int query(int x, int k) {
    int cur = 0;
    int res = INT_MAX;
    for (int i=LOG;i>=0;i--) {
        if(cur==-1) break;
        int xb = (x >> i) & 1;
        int kb = (k >> i) & 1;
        if(kb==1) cur=trie[cur].child[xb^1];
        else {
            int good=trie[cur].child[xb^1];
            if (good!=-1) 
                res=min(res, trie[good].mn);
            cur=trie[cur].child[xb];
        }
    }
    if(cur!=-1) res=min(res, trie[cur].mn);
    return res;
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; int x;
    cin >> n >> x;
    vector<int> a(n + 1), px(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    trie.reserve(MAXN * 32);
    trie.push_back(Node());
    insert(0, 0);
    int vt=0, ans=1;
    for(int i=1;i<=n;i++) {
        px[i]=px[i-1]^a[i];
        int j=query(px[i], x);
        if(j!=INT_MAX)
            if(i-j>vt || (i-j==vt && j+1<ans)){
                vt=i-j;
                ans=j+1;
            }
        insert(px[i], i);
    }
    cout<<ans<<" "<<vt;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...