Cod sursa(job #2098775)

Utilizator anisca22Ana Baltaretu anisca22 Data 3 ianuarie 2018 15:03:44
Problema Xor Max Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define TMAX 2
using namespace std;

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

int N, mx = -1, start, finish;
int Sp[NMAX];

struct TRIE
{
    int terminal;
    TRIE *son[TMAX];
    TRIE()
    {
        terminal = 0;
        memset(son, 0, sizeof(son));
    }
};

TRIE *root = new TRIE();

void add_number(TRIE *nod, int put, int num, int poz)
{
    if (put == -1)
    {
        nod -> terminal = poz;
        return;
    }

    bool bit = num & (1 << put);
    if (nod -> son[bit] == 0)
        nod -> son[bit] = new TRIE();
    add_number(nod -> son[bit], put - 1, num, poz);
}

int caut(TRIE *nod, int put, int num)
{
    if (put == -1)
        return nod -> terminal;

    bool bit = num & (1 << put);
    if (nod -> son[!bit] == 0)
        return caut(nod -> son[bit], put - 1, num);
    return caut(nod -> son[!bit], put - 1, num);
}

int main()
{
    add_number(root, 21, 0, 0);
    fin >> N;
    for (int i = 1; i <= N; i++)
    {
        int nr;
        fin >> nr;
        Sp[i] = Sp[i - 1] ^ nr;
        int poz = caut(root, 21, Sp[i]);
        int act = Sp[i] ^ Sp[poz];
        if (act > mx)
        {
            mx = act;
            start = poz + 1;
            finish = i;
        }
        add_number(root, 21, nr, i);
    }
    fout << mx << " " << start << " " << finish;
    fin.close();
    fout.close();
    return 0;
}