Cod sursa(job #1529257)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 20 noiembrie 2015 17:49:38
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <bits/stdc++.h>

#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013

using namespace std;

struct Trie
{
    int pos;
    Trie *f[2];

    Trie()
    {
        pos = 0;
        f[0] = f[1] = 0;
    }
};

Trie *T;

int n, i, sum, x, mx, pos1, pos2, pos;
int s[100005];

void Insert(Trie *T, int number, int bit, int val)
{
    if(bit < 0)
    {
        T -> pos = val;
        return;
    }

    int x = (number & (1 << bit)) > 0;
    if(T -> f[x] == 0)
        T -> f[x] = new Trie;
    Insert(T -> f[x], number, bit - 1, val);
}

int Query(Trie *T, int number, int bit)
{
    if(bit < 0)
        return T -> pos;

    int x = (number & (1 << bit)) > 0;
    x = 1 - x;
    if(T -> f[x] == 0)
        return Query(T -> f[1 - x], number, bit - 1);
    return Query(T -> f[x], number, bit - 1);
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);

    scanf("%d", &n);

    T = new Trie;
    Insert(T, 0, 20, 0);

    sum = s[0] = 0;
    mx = pos1 = pos2 = -1;

    for(i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        sum ^= x;
        s[i] = sum;

        pos = Query(T, sum, 20);
        if(mx < (sum ^ s[pos]))
        {
            mx = sum ^ s[pos];
            pos1 = pos + 1;
            pos2 = i;
        }

        Insert(T, sum, 20, i);
    }

    printf("%d %d %d", mx, pos1, pos2);

    return 0;
}