Cod sursa(job #2399151)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 7 aprilie 2019 00:18:35
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>

using namespace std;

ifstream fin("xormax.in");
ofstream fout("xormax.out");

struct str{int val; int poz;};

struct Trie
{
    str Det;
    Trie* son[2];

    Trie() { Det = {0, 0}, son[0] = son[1] = 0;}
};

Trie * Root = new Trie;

int N, Sol = -1, Ans , st, dr;

void Insert(Trie * & Nod, int x, int p, int lev)
{
    if(lev >= 0)
    {
        bool c = x & (1 << lev);

        if(Nod -> son[c] == 0)
            Nod -> son[c] = new Trie;

        Insert(Nod -> son[c], x, p, lev - 1);
    }
    else Nod -> Det.val = x, Nod -> Det.poz = p;
}

str Find(Trie * & Nod, int x, int lev)
{
    if(lev >= 0)
    {
        bool c = x & (1 << lev);

        if(Nod -> son[!c])
            return Find(Nod -> son[!c], x, lev - 1);
        else
            return Find(Nod -> son[ c], x, lev - 1);
    }
    else return Nod -> Det;
}

int main()
{
    fin >> N; Insert(Root, 0, 0, 22);

    for(int i = 1, x; i <= N; i++)
    {
        fin >> x, Ans ^= x; str S = Find(Root, Ans, 22); S.val ^= Ans;

        if(S.val > Sol)
            Sol = S.val, st = S.poz + 1, dr = i;

        Insert(Root, Ans, i, 22);
    }
    fout << Sol << " " << st << " " << dr << '\n';

    fout.close();
    fin.close();

    return 0;
}