Cod sursa(job #2853049)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 19 februarie 2022 20:24:44
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int NMAX=100005, nrmax=21;

int N, v[NMAX], sum[NMAX], st;

struct trieNode{
    int ind; ///indicele ultimului numar care se termina in acest nod
    trieNode *next[2];
    trieNode(){
        ind=0;
        next[0]=NULL;
        next[1]=NULL;
    }
};

void addTrie(trieNode *node, int val, int poz, int i){
    if(poz<0){
        node->ind=i;
        return;
    }
    int nextIndex=((val>>poz)&1);
    if(node->next[nextIndex]==NULL)
        node->next[nextIndex]=new trieNode;
    addTrie(node->next[nextIndex],val,poz-1,i);
}

int searchTrie(trieNode *node, int val, int poz){
    if(poz<0){
        st=node->ind;
        return 0;
    }
    int bit=((val>>poz)&1);
    if(node->next[1-bit]!=NULL)
        return (1<<poz)+searchTrie(node->next[1-bit],val,poz-1);
    else
        return searchTrie(node->next[bit],val,poz-1);
}

int main()
{
    int sol=-1, p1=0, p2=0;
    trieNode *start=new trieNode;
    fin>>N;
    for(int i=1;i<=N;i++){
        fin>>v[i];
        sum[i]=sum[i-1]^v[i];
    }
    addTrie(start,0,nrmax,0);

    for(int i=1;i<=N;i++){
        int num=searchTrie(start,sum[i],nrmax);
        if(num>sol){
            sol=num;
            p1=st;
            p2=i;
        }
        addTrie(start,sum[i],nrmax,i);
    }

    fout<<sol<<' '<<p1+1<<' '<<p2;

    fin.close();
    fout.close();
    return 0;
}