Cod sursa(job #1881595)

Utilizator cella.florescuCella Florescu cella.florescu Data 16 februarie 2017 16:43:35
Problema Xor Max Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectiile9_10_11_12_13 Marime 1.23 kb
#include <cstdio>
#define MAXN 200000
#define P2MAX 2097152

using namespace std;

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

Trie *t=new Trie;
int xorp[MAXN+1];

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

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

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