Cod sursa(job #1591804)

Utilizator timicsIoana Tamas timics Data 6 februarie 2016 18:47:05
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<stdio.h>
#include<bitset>
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define MOD 1000000007
using namespace std;
int N,x,par;
string s,t;
int ma, lma=1, rma=1, cnt;
int l[3000100], r[3000100], ind[3000100];

inline void add(int j, int x) {
    bool ok = (x == 765164);
    int curr = 0;
    for(int i=20;i>=0;--i) {
        if(x < (1<<i)) {
            if(!l[curr]) {
                l[curr] = ++cnt;
            }
            curr = l[curr];
        } else {
            x -= (1<<i);
            if(!r[curr]) {
                r[curr] = ++cnt;
            }
            curr = r[curr];
        }
    }

    ind[curr] = j;
}

inline void compute(int j, int x) {
    int curr = 0, ret = 0;
    for(int i=20;i>=0;--i) {
        if(x >= (1<<i)) {
            if(!l[curr]) {
                curr = r[curr];
            } else {
                curr = l[curr];
                ret += (1<<i);
            }
            x -= (1<<i);
        } else {
            if(!r[curr]) {
                curr = l[curr];
            } else {
                curr = r[curr];
                ret += (1<<i);
            }
        }
    }
    if(ret > ma) {
        ma = ret;
        lma = ind[curr]+1;
        rma = j;
    }
}

int main() {
	freopen("xormax.in","r",stdin);
	freopen("xormax.out","w",stdout);
	//freopen("input.in","r",stdin);
    scanf("%d",&N);
    for(int i=0;i<=N;++i) {
        if(i) {
            scanf("%d",&x);
            par = (par ^ x);
            x = par;
            compute(i,par);

        }
        add(i,par);
    }
    printf("%d %d %d\n",ma,lma,rma);
    return 0;
}