Cod sursa(job #2063952)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 11 noiembrie 2017 17:27:54
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>

using namespace std;

FILE *in,*out;

int v[100005];

struct Trie
{
    int pos;
    Trie* son[2];
};

Trie* root;

void addtrie(Trie* node,int x,int nrbit,int i)
{
    if(nrbit < 0)
    {
        node -> pos = i;
    }
    else
    {
        int byte = (x >> nrbit) & 1;
        if(node -> son[byte] == NULL)
        {
            node -> son[byte] = new Trie();
            node -> pos = -1;
        }
        addtrie(node -> son[byte],x,nrbit-1,i);
    }
}

int solve(Trie* node,int x,int nrbit)
{
    if(nrbit < 0)
    {
        return node -> pos;
    }
    else
    {
        int byte = 1 - ((x >> nrbit) & 1);
        if(node -> son[byte] != NULL)
            return solve(node -> son[byte],x,nrbit-1);
        else
            return solve(node -> son[1-byte],x,nrbit-1);
    }
}

int main()
{
    in = fopen("xormax.in","r");
    out = fopen("xormax.out","w");
    int n;
    fscanf(in,"%d",&n);
    root = new Trie();
    int maxim = -1,st,dr;
    addtrie(root,0,21,0);
    for(int i = 1; i <= n; i ++)
    {
        fscanf(in,"%d",&v[i]);
        v[i] ^= v[i-1];
        addtrie(root,v[i],21,i);
        int pretender = solve(root,v[i],21);
        if(v[i] ^ v[pretender] > maxim)
        {
            maxim = v[i] ^ v[pretender];
            st = pretender + 1;
            dr = i;
        }
    }
    fprintf(out,"%d %d %d",maxim,st,dr);
    return 0;
}