Submission #482809

#TimeUsernameProblemLanguageResultExecution timeMemory
482809FatihSolakXOR (IZhO12_xor)C++17
0 / 100
1 ms332 KiB
#include <bits/stdc++.h>
#define N 250005
#define K 29
using namespace std;
struct node{
    int val=0,l=0,r=0;
};
node trie[N * K];
int arr[N];
int cnt = 1;
void add(int x,int pos){
    int now = 1;
    for(int i=0;i<=K;i++){
        if((1<<(K-i)) & x){
            if(trie[now].r == 0)trie[now].r = ++cnt;
            now = trie[now].r;
        }
        else{
            if(trie[now].l == 0)trie[now].l = ++cnt;
            now = trie[now].l;
        }
        trie[now].val = max(trie[now].val,pos);
    }
}
void solve(){
    int n,x;
    cin >> n >> x;
    for(int i=1;i<=n;i++)cin >> arr[i];
    int xr = 0;
    int ans = 0;
    int pos = 0;
    for(int i=n;i>=1;i--){
        xr ^= arr[i];
        int maxi = 0;
        if(xr >= x)maxi = n+1;
        add(arr[i],i);
        int now = 1;
        int mask = 0;
        for(int j=0;j<=K;j++){
            if( ( 1<<(K-j)) & arr[i] ){
                if((mask ^ ((1<<(K - j)) - 1)) < x){
                    now = trie[now].l;
                }
                else{
                    maxi = max(maxi, trie[trie[now].l].val);
                    mask ^= (1<<(K-j));
                    now = trie[now].r;
                }
            }
            else{
                if( (mask ^ (1<<(K-j)) ^ arr[i]) >= x){
                    maxi = max(maxi, trie[trie[now].r].val);
                    now = trie[now].l;
                }
                else{
                    maxi = max(maxi, trie[trie[now].l].val);
                    mask ^= (1<<(K-j));
                    now = trie[now].r;
                }
            }
            //cout << i << " " << mask << endl;
            if(now == 0)break;
        }
        //cout << i << " " << maxi << endl;
        if(ans <= maxi - i){
            ans = maxi - i;
            pos  = i;
        }
    }   
    cout << pos << " " << ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}
#Verdict Execution timeMemoryGrader output
Fetching results...