Cod sursa(job #1752545)

Utilizator cella.florescuCella Florescu cella.florescu Data 4 septembrie 2016 13:35:19
Problema Xor Max Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#define P2MAX 1048576

using namespace std;

struct Trie{
  int pos;
  Trie *son[2];
  Trie(){
    son[0]=son[1]=0;
  }
};

Trie *t=new Trie;

int nr, i, rez, x;

void add(Trie *node, int p2){
  if(p2==0){
    node->pos=i;
    return;
  }
  if(node->son[(nr&p2)>0]==NULL)
    node->son[(nr&p2)>0]=new Trie;
  add(node->son[(nr&p2)>0], p2>>1);
}

int maxxor(Trie *node, int p2){
  if(p2==0)
    return node->pos;
  if(node->son[1-((x&p2)>0)]!=NULL){
    rez+=p2;
    return maxxor(node->son[1-((x&p2)>0)], p2>>1);
  }
  return maxxor(node->son[(x&p2)>0], p2>>1);
}

int main()
{
    FILE *fin, *fout;
    int n, maxim, maxst, maxdr, p;
    fin=fopen("xormax.in", "r");
    fscanf(fin, "%d", &n);
    i=nr=0; maxim=-1;
    add(t, P2MAX);
    for(i=1; i<=n; i++){
      fscanf(fin, "%d", &x);
      rez=0;
      p=maxxor(t, P2MAX);
      if(rez>maxim){
        maxim=rez; maxst=p+1; maxdr=i;
      }
      nr^=x;
      add(t, P2MAX);
    }
    fclose(fin);
    fout=fopen("xormax.out", "w");
    fprintf(fout, "%d %d %d\n", maxim, maxst, maxdr);
    fclose(fout);
    return 0;
}