Cod sursa(job #1140620)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 12 martie 2014 09:46:51
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
using namespace std;

struct trie {
    int x;
    trie *p[2];
    trie() {
        p[0] = p[1] = NULL;
    }
};

trie r;
int n;
int mxv=-1,mxs,mxf;
int next, last;
int xr;

void insert(int pos) {
    trie *t = &r;
    for (int i=25;i>=0;i--) {
        if (((1<<i) bitand xr) != 0) {
            if (t->p[1] == NULL) t->p[1] = new trie();
            t = t->p[1];
        } else {
            if (t->p[0] == NULL) t->p[0] = new trie();
            t = t->p[0];
        }
    }
    t->x = pos;
}

void check(int fin) {
    trie *t = &r;
    int xorvalue = 0;
    for (int i=25;i>=0;i--) {
        int h = ((1<<i) bitand xr) != 0;
        if (t->p[1-h] != NULL) {
            t = t->p[1-h];
            xorvalue = (xorvalue<<1) + 1;
        }
        else if (t->p[h] != NULL) {
            t = t->p[h];
            xorvalue = xorvalue<<1;
        }
    }
    if (xorvalue > mxv) {
        mxv = xorvalue;
        mxs = t->x+1;
        mxf = fin;
    }
}

int main() {
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);
    scanf("%d",&n);
    insert(0);
    for (int i=1;i<=n;i++) {
        scanf("%d",&next);
        xr = xr xor next;
        check(i);
        insert(i);
    }
    printf("%d %d %d\n",mxv,mxs,mxf);
    return 0;
}