Cod sursa(job #2536128)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 1 februarie 2020 15:28:15
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<bits/stdc++.h>
using namespace std;
struct TrieNode{
  TrieNode *children[2];
  TrieNode (){
    children[0]=children[1]=NULL;
  }
};
TrieNode *root= new TrieNode;
void ins(TrieNode *node,int x,int p){
  if(p<0)
    return;
  int b= (x &(1<<p))>>p;
  if(node->children[b]==NULL){
    node->children[b] = new TrieNode;
  }
  ins(node->children[b],x,p-1);
}
int query(TrieNode *node,int x,int p){
  if(p<0)
    return 0;
  int b= (x &(1<<p))>>p;
  b^=1;
  if(node->children[b]!=NULL){
    return (1<<p) + query(node->children[b],x,p-1);
  }
  else{
    return query(node->children[b^1],x,p-1);
  }
}
const int N=100005;
int v[N];
int main()
{
  FILE*fin,*fout;
  fin=fopen("xormax.in","r");
  fout=fopen("xormax.out","w");
  int n;
  fscanf(fin,"%d",&n);
  int ansmax=-1,sum=0,poz=0;
  ins(root,sum,21);
  for(int i=1;i<=n;i++){
    fscanf(fin,"%d",&v[i]);
    sum^=v[i];
    int mx=query(root,sum,21);
    if(mx>ansmax){
      ansmax=mx;
      poz=i;
    }
    ins(root,sum,21);
  }
  int st=poz;
  sum=0;
  while(st>=1 && sum!=ansmax){
    sum^=v[st];
    st--;
  }
  fprintf(fout,"%d %d %d",ansmax,st+1,poz);
  return 0;
}