Cod sursa(job #2303214)

Utilizator racheriunicolaechowchow racheriunicolae Data 15 decembrie 2018 20:33:31
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>

using namespace std;
const int INTSIZE = 31;
struct trie
{
    int val , poz;
    trie *nxt[2];
    trie()
    {
        val = 0;
        nxt[0] = nxt[1] = 0;
    }
};
void add(trie *p , int pre , int ind)
{
    int i;
    for(i = INTSIZE ; i >=0 ; i--)
    {
        bool res = (1 << i) & pre;

        if(p -> nxt[res] == NULL)
            p -> nxt[res] = new trie();

        p = p -> nxt[res];
    }
    p -> val = pre;
    p -> poz = ind;
}
pair <int ,int>  query(trie *p , int pre)
{
    int i;
    for(i = INTSIZE ; i >= 0; i--)
    {
        bool res = pre & (1 << i);

        if(p -> nxt[1 - res] != NULL)
            p = p -> nxt[1 - res];

        else if(p -> nxt[res] != NULL)
            p = p -> nxt[res];
    }
    return {(pre ^ (p -> val)) , p -> poz + 1};
}
const int NMAX = 1e5 + 5;
int n , i , v[NMAX] , pre, ans , st , dr;
pair <int , int > val;
int main()
{
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    trie *p = new trie();
    add(p , 0 , 0);
    fin >> n;
    for(i = 1; i <= n; i++)
    {
        fin >> v[i];
        pre = pre ^ v[i];
        add(p , pre , i);;
        val = query(p , pre);
        if(val.first > ans)
        {
            ans = val.first;
            st = val.second;
            dr = i;
        }
        if(pre > ans)
        {
            ans = pre;
            st = 1;
            dr = i;
        }
    }
    fout << ans << " " << st << " " << dr << "\n";
    return 0;
}
///