Cod sursa(job #2188304)

Utilizator ciprianprohozescuProhozescu Ciprian ciprianprohozescu Data 27 martie 2018 08:39:31
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#define NMAX 100010
#define PMAX 21

using namespace std;

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

struct trie
{
    trie *fiu[2];
    int poz;

    trie()
    {
        fiu[0] = fiu[1] = 0;
        poz = 0;
    }
};
struct solutie
{
    int s, st, dr;
};

int n, v[NMAX];
trie *t = new trie;
solutie sol;

void inserare(trie *nod, int k, int x, int i);
bool cautare(trie *nod, int k, int x, int s, int i);

int main()
{
    int i, x;
    fin >> n;
    sol.s = -1;
    inserare(t, (1 << PMAX), 0, 0);
    for (i = 1; i <= n; i++)
    {
        fin >> x;
        v[i] = v[i - 1] ^ x;
        cautare(t, (1 << PMAX), v[i], 0, i);
        inserare(t, (1 << PMAX), v[i], i);
    }
    fout << sol.s << ' ' << sol.st << ' ' << sol.dr << '\n';
    fout.close();
    return 0;
}

void inserare(trie *nod, int k, int x, int i)
{
    if (!k)
    {
        nod->poz = i;
        return ;
    }
    if (nod->fiu[(x & k) || 0] == 0)
        nod->fiu[(x & k) || 0] = new trie;
    inserare(nod->fiu[(x & k) || 0], (k >> 1), x, i);
}
bool cautare(trie *nod, int k, int x, int s, int i)
{
    bool gasit = 0, urm;
    if (!k)
    {
        if (s > sol.s)
        {
            sol.s = s;
            sol.dr = i;
            sol.st = nod->poz + 1;
        }
        return 1;
    }
    urm = (x & k) || 0;
    if (nod->fiu[!urm])
        gasit = cautare(nod->fiu[!urm], (k >> 1), x, s + k, i);
    if (!gasit && nod->fiu[urm])
        gasit = cautare(nod->fiu[urm], (k >> 1), x, s, i);
    return gasit;
}