Submission #482964

#	Time	Username	Problem	Language	Result	Execution time	Memory
482964		FatihSolak	XOR (IZhO12_xor)	C++17	100 / 100	133 ms	24256 KiB

xor

#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(xr,i);
        int now = 1;
        for(int j=0;j<=K;j++){
            if( (xr & (1<<(K-j))) == (x & (1<<(K-j)))){
                if(!(x & (1<<(K-j)))){
                    maxi = max(maxi,trie[trie[now].r].val);
                }
                now = trie[now].l;
            }
            else{
                if(!(x & (1<<(K-j)))){
                    maxi = max(maxi,trie[trie[now].l].val);
                }
                now = trie[now].r;
            }
            if(now == 0)break;
        }
        maxi = max(maxi,trie[now].val);
        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
}

• Subtask 1: 100 / 100