Cod sursa(job #1529261)

Utilizator bogdan10bosBogdan Sitaru bogdan10bos Data 20 noiembrie 2015 17:50:46
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 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);
}

class Reader
{
private:
    char buff[100805];
    int buffer, cnt;

public:
    Reader()
    {
        buffer = 1 << 15;
        cnt = buffer - 1;
    }

    char gChar()
    {
        if(++cnt == buffer)
        {
            cnt = 0;
            fread(buff, buffer, 1, stdin);
        }
        return buff[cnt];
    }

    int gInt()
    {
        int nr = 0;
        char ch = gChar();
        while(ch < '0' || '9' < ch)
            ch = gChar();
        while('0' <= ch && ch <= '9')
        {
            nr = nr * 10 + ch - '0';
            ch = gChar();
        }
        return nr;
    }
};
Reader rdr;

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

    n = rdr.gInt();

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

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

    for(i = 1; i <= n; i++)
    {
        x = rdr.gInt();
        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;
}