Cod sursa(job #1686346)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 12 aprilie 2016 10:52:21
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int n;
int Ans, start, stop;
bool f[(1<<21)];

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

void AddToTrie(TrieNode *node, int str, int length, int CurrentPosition, int Pos)
{
    if(length == CurrentPosition)
    {
        node->NrWord = true;
        node->pos = Pos;
    }
    else
    {
        bool Next = str&(1<<(length-CurrentPosition-1));
        if(node->sons[Next]==NULL)
            node->sons[Next] = new TrieNode;
        AddToTrie(node->sons[Next], str, length, CurrentPosition+1, Pos);
    }
}

void Query(TrieNode *node, int str, int length, int CurrentPosition, int CurrentString, int Pos)
{
    if(f[CurrentString])
    {
        if(str^CurrentString>Ans)
        {
            Ans = max(Ans, str^CurrentString);
            stop = Pos;
            start = node->pos;
        }
        else if(str^CurrentString == Ans && stop == Pos)
        {
            start = max(start, node->pos);
        }
    }
    if(length == CurrentPosition)
        return;
    bool Next = str&(1<<(length-CurrentPosition-1))>0;
    if(node->sons[!Next]!=NULL)
    {
        CurrentString+=(!Next)*(1<<(length-CurrentPosition-1));
        Query(node->sons[!Next], str, length, CurrentPosition+1, CurrentString, Pos);
    }
    else if(node->sons[Next]!=NULL)
    {
        CurrentString+=Next*(1<<(length-CurrentPosition-1));
        Query(node->sons[Next], str, length, CurrentPosition+1, CurrentString, Pos);
    }
}

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;
    for(int i=1; i<=n; i++)
    {
        int x;
        scanf("%d", &x);
        Xor^=x;
        Query(root, Xor, 21, 0, 0, i);
        AddToTrie(root, Xor, 21, 0, i);
        f[Xor] = true;
    }
    printf("%d %d %d\n", Ans, start+1, stop);
    return 0;
}