Cod sursa(job #2010401)

Utilizator victoreVictor Popa victore Data 12 august 2017 22:57:20
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

typedef pair<int,int> ii;

struct Trie
{
    Trie *fii[2];
    int last=0;
    Trie()
    {
        memset(fii,0,sizeof(fii));
    }
};

Trie *mainroot = new Trie;

inline void add(Trie* root,int x,int p2,int poz)
{
    if(p2==0)
    {
        root->last=poz;
        return;
    }
    int bit=x&p2;
    if(bit)
        bit=1;
    if(root->fii[bit] == 0)
        root->fii[bit] = new Trie;
    add(root->fii[bit],x,p2>>1,poz);
}

ii query(Trie* root, int x, int p2)
{
    if(p2==0)
        return ii(0,root->last);
    int bit=x&p2;
    if(bit)
        bit=1;
    ii val= ii(0,0);
    if(root->fii[1^bit] != 0)
    {
        val=query(root->fii[1^bit],x,p2>>1);
        val.first+=(1^bit) * p2;
    }
    else
    {
        val=query(root->fii[bit] , x, p2>>1);
        val.first+=(bit)*p2;
    }
    return val;
}

int main()
{
    ii t;
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    int n,x=0,best=0,y=1,curr=0,i,a;
    scanf("%d",&n);
    add(mainroot,0,(1<<21),0);
    for(i=1;i<=n;++i)
    {
        scanf("%d",&a);
        curr^=a;
        add(mainroot,curr,(1<<21),i);
        t=query(mainroot,curr,(1<<21));
        t.first^=curr;
        if(t.first>best)
        {
            best=t.first;
            x=t.second;
            y=i;
        }
    }
    printf("%d %d %d",best,x+1,y);
}