Cod sursa(job #766291)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 10 iulie 2012 21:14:17
Problema Xor Max Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include <algorithm>
using namespace std;

struct trie {
    trie *left;
    trie *right;
    int index;

};

trie *radacina = new trie;

const int N = 100005;
const int nrb = 25;
int n, a, xorp, maxsol, ind, ind2, SOL;

void add(int x, int id)
{
    trie *p = radacina;
    for(int i = nrb - 1; i >= 0; --i) {
        if(((x >> i) & 1) == 0) {
            if(p->left == NULL) {
                p->left = new trie;
            }
            p = p->left;
        }
        else {
            if(p->right == NULL)
                p->right = new trie;
            p = p->right;
        }
    }
    p->index = id;
}

void cauta(int x, int id)
{
    int sol = 0;
    trie *p = radacina;
    for(int i = nrb - 1; i >= 0; --i) {
        if(((x >> i) & 1) == 1) {
            if(p->left != NULL) {
                p = p->left;
                sol += 1 << i;
            }
            else p = p->right;
        }
        else {
            if(p->right != NULL) {
                p = p->right;
                sol += 1 << i;
            }
            else p = p->left;
        }
    }
    if((sol > maxsol) || (sol == maxsol && ind - ind2 > id - (p->index))) {
        maxsol = sol;
        ind = id;
        ind2 = p->index;
    }
}

int main()
{
    freopen ("xormax.in", "r", stdin);
    freopen ("xormax.out", "w", stdout);
    scanf("%d", &n);
    add(0, 1);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a);
        xorp ^= a;
        cauta(xorp, i);
        add(xorp, i + 1);
    }
    printf("%d %d %d\n", maxsol, ind2, ind);
    return 0;

}