Cod sursa(job #1766494)

Utilizator TibixbAndrei Tiberiu Tibixb Data 27 septembrie 2016 23:32:36
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<fstream>
#define NMAX 100005
using namespace std;
int n, i, x, s[NMAX], y, leftPoz, h, sol, st, dr;
ifstream cin("xormax.in");
ofstream cout("xormax.out");

struct trie
{
    trie *f[2];
    int poz;
    trie()
    {
        f[0] = f[1] = 0;
        poz = 0;
    }
};

trie *rad;

void insert_trie(trie *nod, int bit, int val, int poz)
{
    if(bit == -1)
    {
        nod -> poz = poz;
        return ;
    }
    if((val>>bit) & 1 == 1)
    {
        if(nod -> f[1] == NULL)
        {
            nod -> f[1] = new trie;
        }
        insert_trie(nod -> f[1], bit - 1, val, poz);
    }else
    {
        if(nod -> f[0] == NULL)
        {
            nod -> f[0] = new trie;
        }
        insert_trie(nod -> f[0], bit - 1, val, poz);
    }

}

void search_trie(trie *nod, int bit, int val)
{
    if(bit == -1)
    {
        leftPoz= nod -> poz;
        return ;
    }
    int searched_bit = 1 - (val>>bit) & 1;
    if(nod -> f[searched_bit] == 0)
    {
        search_trie(nod -> f[1 - searched_bit], bit - 1, val);
    }else
    {
        search_trie(nod -> f[searched_bit], bit - 1, val);
    }
}

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        cin >> x;
        s[i] = s[i - 1] ^ x;

        y = max(y, s[i]);
    }

    while(y != 0)
    {
        y /= 2;
        h++;
    }

    rad = new trie;

    insert_trie(rad, h, 0, 0);


    for(int i = 1; i <= n; i++)
    {
        search_trie(rad, h, s[i]);

        if((s[i] ^ s[leftPoz]) > sol)
        {
            sol = s[i] ^ s[leftPoz]; st = leftPoz + 1; dr = i;
        }

        insert_trie(rad, h, s[i], i);
    }
    cout << sol << " " << st << " " << dr;
    return 0;
}