Cod sursa(job #3351744)

Utilizator vladneaguVladneagu vladneagu Data 21 aprilie 2026 11:16:31
Problema Xor Max Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int prefxor[maxn];
struct Node{
    int act;
    int endd;
    vector<int> next;
    Node(){
        act=0;
        endd=0;
        next.assign(2,-1);
    }
};
struct Trie{
    vector<Node> t;
    Trie(){
        t.push_back(Node());
    }
    void insertt(int nr,int idd){
        int u=0;
        t[u].act+=1;
        for(int i=21;i>=0;i--){
            bool val=(((1<<i)&nr)>0);
            if(t[u].next[val]==-1){
                t[u].next[val]=t.size();
                t.push_back(Node());
            }
            u=t[u].next[val];
            t[u].act+=1;
        }
        t[u].endd=idd;
    }
    pair<int,int> calc(int nr){
        int u=0;
        int x=0;
        for(int i=21;i>=0;i--){
            bool val=1-(((1<<i)&nr)>0);
            //cout<<i<<" "<<nr<<" "<<val<<endl;
            if(t[u].next[val]!=-1){
                x+=val*(1<<i);
                u=t[u].next[val];
            }else{
                val=1-val;
                //if(t[u].endd)return x;
                x+=val*(1<<i);
                u=t[u].next[val];
            }
        }
        return {x,t[u].endd};
    }
};
signed main()
{
    ifstream cin("xormax.in");
    ofstream cout("xormax.out");
    Trie trie;
    int n;
    cin>>n;
    int maxi=-1;
    int l,r;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        prefxor[i]=prefxor[i-1]^x;
        if(prefxor[i]>maxi){
            maxi=prefxor[i];
            l=1;
            r=i;
        }
    }
    for(int i=n;i>=1;i--){
        trie.insertt(prefxor[i],i);
        int best,idd;
        tie(best,idd)=trie.calc(prefxor[i]);
        if((best^prefxor[i])>maxi || (maxi==(best^prefxor[i]) && idd<r) || (maxi==(best^prefxor[i]) && idd==r && (r-l+1)>idd-i)){
            l=i+1;
            r=idd;
            maxi=best^prefxor[i];
        }
    }
    cout<<maxi<<" "<<l<<" "<<r;
    return 0;
}