Cod sursa(job #1471823)

Utilizator SilviuIIon Silviu SilviuI Data 15 august 2015 12:56:22
Problema Xor Max Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 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; }
inline int abss(int a) { if (a<0) return (-a); else return a; }
void add_trie(int x)
{
    int t[40]={0},i=0,nr=1; trie* a=root;
    while (x>0) { i++; t[i]=x%2; x=x/2; }
    for (int j=1;j<=maxx/2;j++) swap(t[j],t[maxx-j+1]); i=maxx;
    while (nr<=i && a->t[t[nr]]!=NULL) { a=a->t[t[nr]]; nr++; }
    for (;nr<=i;nr++) {
        a->t[t[nr]]=new trie; a=a->t[t[nr]];
    }
    if (a->x==0) a->x=p;
}
void find_trie(int x)
{
    int t[40]={0},i=0,value=0,nr=1; trie* a=root;
    while (x>0) { i++; t[i]=x%2; x=x/2; }
    for (int j=1;j<=maxx/2;j++) swap(t[j],t[maxx-j+1]); i=maxx;
    while (nr<=i) {
        if (a->t[1-t[nr]]!=NULL) value=value+put2[i-nr],a=a->t[1-t[nr]]; else
            a=a->t[t[nr]];
        nr++;
    }
    if (value>sol) {
        sol=value; st=min(a->x,p); dr=max(a->x,p);
    } else
    if (value==sol && max(a->x,p)<dr) { st=min(a->x,p); dr=max(a->x,p); } else
    if (value==sol && dr-st+1>abss(a->x-p)+1) {
        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;
for (i=1;i<=n;i++) { sum[i]=(sum[i-1]^t[i]); maxx=max(sum[i],maxx); }
maxx=trunc(log2(maxx))+1;
for (i=1;i<=n;i++) { p=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;
}