Cod sursa(job #1791023)

Utilizator mariakKapros Maria mariak Data 28 octombrie 2016 23:22:41
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>
#define Nmax 100002
FILE *fin  = freopen("xormax.in", "r", stdin);
FILE *fout = freopen("xormax.out", "w", stdout);

using namespace std;
int n, s[Nmax], sol, l, r;
struct TrieNode
{
    TrieNode *son[2];
    int ind;

    TrieNode() {
        ind = -1;
        son[0] = son[1] = NULL;
    }
};
void insert(TrieNode *node, int x, int ind, int b = 21)
{
    if(b == -1)
    {
        node->ind = ind;
        return;
    }
    int val = (x >> b) & 1;
    if(node->son[val] == NULL)
        node->son[val] = new TrieNode();
    insert(node->son[val], x, ind, b - 1);
}
int query(TrieNode *node, int x, int b = 21)
{
    if(b == -1)
        return node->ind;
    int val = (x >> b) & 1;
    if(node->son[1 - val] != NULL)
        val = 1 - val;
    query(node->son[val], x, b - 1);
}
void update(int left, int right)
{
   if(sol < (s[right] ^ s[left]))
   {
       sol = s[right] ^ s[left];
       l = left + 1;
       r = right;
   }
}
int main()
{
    int x, pos;
    TrieNode *root = new TrieNode();

    scanf("%d", &n);
    insert(root, 0, 0);

    for(int i = 1; i <= n; ++ i)
    {
        scanf("%d", &x);
        s[i] = s[i - 1] ^ x;
        pos = query(root, s[i]);
        insert(root, s[i], i);
        update(pos, i);
    }
    printf("%d %d %d\n", sol, l, r);
}