Cod sursa(job #1694728)

Utilizator razvandRazvan Dumitru razvand Data 25 aprilie 2016 21:20:08
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
#define B 21
#define MAX 100003

using namespace std;

struct trie {
    trie *t0;
    trie *t1;
    int p;
};

ifstream in("xormax.in");
ofstream out("xormax.out");

trie *root;
int M[MAX];

void init(trie *&nod) {
    nod = (trie*) malloc(sizeof(trie));
    nod->t0 = NULL;
    nod->t1 = NULL;
    nod->p = -1;
}

trie* ins(trie *nod, int val, int poz, int bit) {
    if(nod == NULL)
        init(nod);
    if(bit == -1) {
        nod->p = poz;
        return nod;
    }
    trie *next;
    if((val&(1<<bit)) == 0) {
        next = ins(nod->t0, val, poz, bit-1);
        nod->t0 = next;
    } else {
        next = ins(nod->t1, val, poz, bit-1);
        nod->t1 = next;
    }
    return nod;
}

int gm(trie *nod, int val, int bit) {

    if(bit == -1)
        return nod->p;

    if((val&(1<<bit)) == 0) {
        if(nod->t1 != NULL) {
            return gm(nod->t1, val, bit-1);
        } else {
            return gm(nod->t0, val, bit-1);
        }
    } else {
        if(nod->t0 != NULL) {
            return gm(nod->t0, val, bit-1);
        } else {
            return gm(nod->t1, val, bit-1);
        }
    }

}

int main() {

    init(root);
    int n,val;
    int X = 0;
    int P;
    int mx = 0;
    int st = 1;
    int en = 1;
    in >> n;
    ins(root, 0, 0, B);

    for(int i = 1; i <= n; i++) {
        in >> val;
        X ^= val;
        M[i] = X;
        ins(root, X, i, B);

        P = gm(root, X, B);
        if(X^M[P] > mx || (X^M[P] == mx && en-st > i-P+1)) {

            mx = X^M[P];
            st = P+1;
            en = i;

        }

    }

    out << mx << " " << st << " " << en << '\n';

    return 0;
}