Cod sursa(job #2307777)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 25 decembrie 2018 17:36:54
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>

using namespace std;

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

int N, xors[100005];
int xormax, st, dr;

class Node{
public:
    Node* fii[2];

    Node()
    {
        fii[0] = NULL;
        fii[1] = NULL;
    }
};

Node* InsertTrie(Node* node, int val, int e)
{
    if(node == NULL)
        node = new Node;

    if(e > 0)
        node-> fii[val & (1 << e)] = InsertTrie(node-> fii[val & (1 << e)], val, e - 1);

    return node;
}

int SearchXorMax(Node* node, int val, int e)
{
    if(e == -1)
        return 0;

    if(node-> fii[!(val & (1 << e))])
        return (1 << e) + SearchXorMax(node-> fii[!(val & (1 << e))], val, e - 1);

    return SearchXorMax(node-> fii[val & (1 << e)], val, e - 1);
}

int main()
{
    fin >> N;

    Node* trie = NULL;
    trie = InsertTrie(trie, 0, 20);

    for(int i = 1; i <= N; i++)
    {
        fin >> xors[i];
        xors[i] ^= xors[i - 1];

        int currentXorMax = SearchXorMax(trie, xors[i], 20);
        if(currentXorMax > xormax)
        {
            xormax = currentXorMax;
            dr = i;
        }

        trie = InsertTrie(trie, xors[i], 20);
    }

    for(int i = dr - 1; i >= 1; i--)
        if((xors[i] ^ xors[dr]) == xormax)
        {
            st = i + 1;
            break;
        }

    fout << xormax << ' ' << st << ' ' << dr;
    return 0;
}