Cod sursa(job #2063980)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 11 noiembrie 2017 17:44:59
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 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 bitt = (x >> nrbit) & 1;
        if(node -> son[bitt] == NULL)
        {
            node -> son[bitt] = new Trie();
            node -> pos = -1;
        }
        addtrie(node -> son[bitt],x,nrbit-1,i);
    }
}

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

int maxim,st,dr;

void update(int from, int to) {
  int pretender = v[from] ^ v[to];
  if(maxim < pretender) {
    maxim = pretender;
    if(from < to) {
      st = from + 1;
      dr = to;
    }
  }
}

int main()
{
    in = fopen("xormax.in","r");
    out = fopen("xormax.out","w");
    int n;
    fscanf(in,"%d",&n);
    root = new Trie();
    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);
        update(pretender,i);
    }
    fprintf(out,"%d %d %d",maxim,st,dr);
    return 0;
}