Cod sursa(job #2307790)

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

using namespace std;

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

class Node{
public:
    int lastIndStopHere;
    Node* fiu[2];

    Node()
    {
        lastIndStopHere = 0;
        fiu[0] = 0;
        fiu[1] = 0;
    }
};

int N, xors[100005];
int xormax, st, dr;
Node* trie = new Node;

void InsertTrie(int val, int index)
{
    Node* node = trie;

    for(int i = 20; i >= 0; i--)
    {
        int bit = ((val & (1 << i)) > 0) ? 1 : 0;

        if(!(node-> fiu[bit]))
            node-> fiu[bit] = new Node;
        node = node-> fiu[bit];
    }

    node-> lastIndStopHere = index;
}

int SearchXorMax(int val)
{
    Node* node = trie;

    for(int i = 20; i >= 0; i--)
    {
        int bit = ((val & (1 << i)) > 0) ? 1 : 0;

        if(node-> fiu[!bit])
            node = node-> fiu[!bit];
        else
            node = node-> fiu[bit];
    }

    return node-> lastIndStopHere;
}

int main()
{
    fin >> N;

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

    xormax = xors[1], st = dr = 1;
    InsertTrie(xors[1], 1);
    for(int i = 2; i <= N; i++)
    {
        int ind = SearchXorMax(xors[i]);
        if((xors[ind] ^ xors[i]) > xormax)
        {
            xormax = (xors[ind] ^ xors[i]);
            st = ind + 1, dr = i;
        }

        InsertTrie(xors[i], i);
    }

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