Cod sursa(job #2098785)

Utilizator anisca22Ana Baltaretu anisca22 Data 3 ianuarie 2018 15:13:11
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>
#define NMAX 100005
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[2];
    TRIE()
    {
        terminal = 0;
        son[0] = 0; son[1] = 0;
    }
};

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, Sp[i], i);

    }
    fout << mx << " " << start << " " << finish;
    fin.close();
    fout.close();
    return 0;
}