Cod sursa(job #2662619)

Utilizator andu2006Alexandru Gheorghies andu2006 Data 24 octombrie 2020 11:52:52
Problema Xor Max Scor 85
Compilator cpp-64 Status done
Runda long-contest-bd-1 Marime 1.39 kb
#include <bits/stdc++.h>
#define NMAX 100003

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct bitTrie{
    struct bt_node{
        int val=-1;
        bt_node *children[2]={NULL,NULL};
    }*root=new bt_node;
    void insert(int x, int val){
        bt_node* curr=root;
        for(int i=20;i>=0;i--){
            if(curr->children[x>>i&1]==NULL)
                curr->children[x>>i&1]=new bt_node;
            curr=curr->children[x>>i&1];
        }
        curr->val=val;
    }
    int getMax(int x){
        bt_node* curr=root;
        for(int i=20;i>=0;i--){
            if(curr->children[!(x>>i&1)]!=NULL){
                curr=curr->children[!(x>>i&1)];
            }
            else{
                curr=curr->children[x>>i&1];
            }
        }
        return curr->val;
    }
}bitwise_trie;
int prefXor[NMAX];
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,x,ans=0,l,r;
    fin>>n;
    bitwise_trie.insert(0,-1);
    for(int i=0;i<n;i++){
        fin>>x;
        prefXor[i]=(i?prefXor[i-1]:0)^x;
        int p=bitwise_trie.getMax(prefXor[i]);
        int Xor=prefXor[i]^(p>=0?prefXor[p]:0);
        if(Xor>ans){
            l=p+2;
            r=i+1;
            ans=Xor;
        }
        bitwise_trie.insert(prefXor[i],i);
    }
    fout<<ans<<" "<<l<<" "<<r;
	return 0;
}