Cod sursa(job #1749702)

Utilizator dani_mocanuDani Mocanu dani_mocanu Data 28 august 2016 16:26:59
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int nmax = 100005;
int N,a[nmax],ans,p1,p2;


struct Trie
{
    Trie *fiu[2];
    int poz;
    Trie()
    {
        poz = 0;
        fiu[0] = fiu[1] = 0;
    }
};
Trie *root = new Trie;
inline void Read()
{
    int i,x;
    fin >> N;
    for(i = 1; i <= N; i++)
    {
        fin >> x;
        a[i] = a[i-1]^x;
    }
}

inline void Add(Trie *nod, int x, int poz, int cnt)
{
    bool bit;
    if(cnt < 0)
    {
        nod -> poz = poz;
        return;
    }
    bit = (x & (1 << cnt));
    if(nod -> fiu[bit] == 0) nod -> fiu[bit] = new Trie;
    Add(nod -> fiu[bit], x, poz, cnt - 1);
}

inline int Find(Trie *nod, int x, int cnt)
{
    if(cnt < 0) return nod -> poz;
    bool bit = (x & (1 << cnt));
    if(nod -> fiu[1-bit] != 0) return Find(nod -> fiu[1-bit],x,cnt-1);
    return Find(nod -> fiu[bit],x,cnt-1);
}

inline void Solve()
{
    int i,j;
    ans = -1;
    Add(root,0,0,22);
    for(i = 1; i <= N; i++)
    {
        j = Find(root,a[i],22);
        if((a[i] ^ a[j]) > ans)
        {
            ans = (a[i] ^ a[j]);
            p1 = j+1, p2 = i;
        }
        Add(root,a[i],i,22);
    }
    fout << ans << " " << p1 << " " << p2 << "\n";
}

int main()
{
    Read();
    Solve();
    fout.close();
    return 0;
}