Cod sursa(job #2882891)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 31 martie 2022 21:40:18
Problema Xor Max Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

const int nmax=1e5+5;
int n;
int v[nmax];
int maxim,maxput;
int start, ende;

struct Trie
{
    int maxpos;
    Trie* fii[2];
    Trie()
    {
        maxpos=-1;
        fii[0]=NULL;
        fii[1]=NULL;
    }
} *root;

void add_to_trie(Trie* t, int i, int p)
{
    if(p==-1) {
        t->maxpos=max(t->maxpos,i);
        return;
    }
    bool pi=( ( (1<<p)&v[i])!=0 );
    if(t->fii[pi]==NULL) t->fii[pi]= new Trie;
    //t->fii[pi].maxpos=max(t->fii[pi].maxpos, i)
    add_to_trie(t->fii[pi], i,p-1);
}

int parcurge_trie(Trie *t, int i, int p)
{
    if(p==-1){
        return t->maxpos;
    }
    bool pi=( ( (1<<p)&v[i])==0 );
    if(t->fii[pi]==NULL)
    {
        return parcurge_trie(t->fii[!pi],i,p-1);
    }
    else return parcurge_trie(t->fii[pi],i,p-1);
}

int main()
{
    root = new Trie;
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i];
        if(maxim<v[i])
        {
            maxim=v[i];
            start=i;
            ende=i;
        }
        v[i]=(v[i]^v[i-1]);
        maxput=max(maxput,(int)log2(v[i]));
    }
    for(int i=0; i<=n; i++)
    {
        add_to_trie(root,i,maxput);
        int elem=parcurge_trie(root, i,maxput);
        if(maxim<(v[elem]^v[i]))
        {
            maxim=v[elem]^v[i];
            start=elem+1;
            ende=i;
        }
    }
    fout<<maxim<<" "<<start<<" "<<ende<<" ";
    return 0;
}