Cod sursa(job #1471809)

Utilizator SilviuIIon Silviu SilviuI Data 15 august 2015 12:20:00
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <stdio.h>
#include <cstring>
#include <limits.h>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <bitset>
#include <string>
#include <vector>
#include <math.h>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <deque>
#define nmax 100010
#define inf 0x3f3f3f3f
#define mp make_pair
using namespace std;
struct trie { int x; trie* t[2];
       trie() {
           int i; x=0;
           for (i=0;i<2;i++) t[i]=NULL;
       }
};
int n,i,t[nmax],sum[nmax],maxx=0,put2[25],sol=0,p,st,dr;
trie* root;
inline int max(int a,int b) { if (a>b) return a; else return b; }
inline int min(int a,int b) { if (a<b) return a; else return b; }
void add_trie(int x)
{
    int t[30]={0},i=0; trie* a=root;
    while (x>0) { i++; t[i]=x%2; x=x/2; } i=maxx;
    for (int j=1;j<=maxx/2;j++) swap(t[j],t[maxx-j+1]);
    while (i>0 && a->t[t[i]]!=NULL) { a=a->t[t[i]]; i--; }
    for (;i>0;i--) {
        a->t[t[i]]=new trie; a=a->t[t[i]];
    }
    a->x=p;
}
void find_trie(int x)
{
    int t[30]={0},i=0,value=0,xx=x; trie* a=root;
    while (x>0) { i++; t[i]=x%2; x=x/2; } i=maxx;
    while (i>0) {
        if (a->t[1-t[i]]!=NULL) value=value+put2[i-1],a=a->t[1-t[i]]; else
            a=a->t[t[i]];
        i--;
    }
    if (value>sol) {
        sol=value; st=min(a->x,p); dr=max(a->x,p);
    }
}
int main() {
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n); root=new trie;
for (i=1;i<=n;i++) scanf("%d",&t[i]),maxx=max(t[i],maxx);
put2[0]=1;
for (i=1;i<=22;i++) put2[i]=put2[i-1]*2;
maxx=trunc(log2(maxx))+1;
for (i=1;i<=n;i++) { p=i; sum[i]=sum[i-1]^t[i]; add_trie(sum[i]); }
for (i=1;i<=n;i++) { p=i; find_trie(sum[i]); }
printf("%d %d %d",sol,st+1,dr);
return 0;
}