Cod sursa(job #2888177)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 10 aprilie 2022 19:17:11
Problema Xor Max Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
//Ilie Dmitru
#include<fstream>
#include<cstdio>
typedef long long int ll;
const int NMAX=100005;
const ll MOD=194767;
const int maxBIT=1<<20;

std::ifstream f("xormax.in");
std::ofstream g("xormax.out");

struct trie
{
    trie* next[2];
    int pos;
};

void init(trie*& t)
{
    t=new trie;
    t->next[0]=t->next[1]=0;
    t->pos=-2;
}

void push(trie*& t, int x, int pos, int bit=maxBIT)
{
    int val=!!(x&bit);
    if(!t)
        init(t);
    if(bit)
        push(t->next[val], x, pos, bit>>1);
    else if(t->pos==-2)
        t->pos=pos;
}

trie* t;

void clear(trie*& t)
{
    if(t)
    {
        clear(t->next[0]);
        clear(t->next[1]);
        delete t;
    }
}

int findMax(trie* t, int x, int& startPos, int bit=maxBIT)
{
    int val=!(x&bit), res=0;
    if(t->next[val])
        res=bit|findMax(t->next[val], x, startPos, bit>>1);
    else if(t->next[!val])
        res=findMax(t->next[!val], x, startPos, bit>>1);
    else
        res=0, startPos=t->pos;
    return res;
}

char s[NMAX*8];
int v[NMAX];

int main()
{
    int i, N, x=0, r, ans=0, pos, bestStart=-1, bestEnd=-1;
    f>>N;
    f.get();
    f.getline(s, NMAX*8);

    for(i=pos=0;s[i];++i)
    {
        if(s[i]!=' ')
            x=x*10+s[i]-'0';
        else
            v[pos++]=x, x=0;
    }
    v[pos]=x;
    push(t, 0, -1);
    x=0;
    for(i=0;i<N;++i)
    {
        x^=v[i];
        r=findMax(t, x, pos);
        push(t, x, i);
        if(r>ans)
        {
            ans=r;
            bestStart=pos;
            bestEnd=i;
        }
    }
    g<<ans<<' '<<bestStart+2<<' '<<bestEnd+1;
    clear(t);
    f.close();
    g.close();
    return 0;
}