Cod sursa(job #1687031)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 12 aprilie 2016 17:11:58
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int Bit = 20;

int n;
int Ans, start, stop;

struct TrieNode
{
	int value;
    int pos;
    TrieNode *sons[2];
    TrieNode() {value=0;pos=0;sons[0]=sons[1]=0;}
};

void AddToTrie(TrieNode *node, int value, int i, int bit)
{
    if(bit < 0)
    {
        node->pos = i;
        node->value = value;
    }
    else
    {
        bool Next = value&(1<<bit);
        if(node->sons[Next]==NULL)
            node->sons[Next] = new TrieNode;
        AddToTrie(node->sons[Next], value, i, bit-1);
    }
}

void Query(TrieNode *node, int queryValue, int i, int bit)
{
    if(bit < 0) {
		if ((queryValue ^ node->value) > Ans) {
			Ans = queryValue ^ node->value;
			start = node->pos;
			stop = i;
		}
		return;
    }
    bool Next = queryValue & (1 << bit);
    if(node->sons[!Next]) {
        Query(node->sons[!Next], queryValue, i, bit - 1);
    }
    else {
        Query(node->sons[Next], queryValue, i, bit-1);
    }
}

TrieNode *root;

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    root = new TrieNode;
    int n;
    scanf("%d", &n);
    int Xor = 0;
    Ans = -1;
    AddToTrie(root,0, 0, 21);
    for(int i=1; i<=n; i++)
    {
        int x;
        scanf("%d", &x);
        Xor^=x;
        Query(root, Xor, i, 21);
        AddToTrie(root, Xor, i, 21);
    }
    printf("%d %d %d\n", Ans, start+1, stop);
    return 0;
}