Cod sursa(job #2307635)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 25 decembrie 2018 10:15:43
Problema Xor Max Scor 0
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <fstream>

using namespace std;

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

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

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

int N, xors[100005];
int bestXor, stBestXor, drBestXor;
bool stSet = false;

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

    if(pas != 20)
        node = InsertTrie(node-> fii[val & 1], val >> 1, pas + 1);

    return node;
}

int SearchBestXor(Node* node, int val, int pas)
{
    if(pas == 20)
        return 0;

    if(node-> fii[!(val & 1)])
        return (1 << pas) + SearchBestXor(node-> fii[!(val & 1)], val >> 1, pas + 1);
    else
        return SearchBestXor(node-> fii[val & 1], val >> 1, pas + 1);
}

int main()
{
    int x;
    Node* trie = NULL;

    fin >> N;

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

    for(int i = 1; i <= N; i++)
    {
        if(i == 1 && xors[i] > bestXor)
        {
            bestXor = xors[i];
            stBestXor = drBestXor = i;
            stSet = true;
        }
        if(i > 1 && (xors[i - 1] ^ xors[i]) > bestXor)
        {
            bestXor = xors[i - 1] ^ xors[i];
            stBestXor = drBestXor = i;
            stSet = true;
        }

        trie = InsertTrie(trie, xors[i], 0);
        int currentBestXor = SearchBestXor(trie, xors[i], 0);

        if(currentBestXor > bestXor)
        {
            bestXor = currentBestXor;
            drBestXor = i;
            stSet = false;
        }
    }

    if(!stSet)
    {
        for(int i = drBestXor - 1; i >= 1; i--)
            if((xors[i] ^ xors[drBestXor]) == bestXor)
            {
                stBestXor = i;
                break;
            }
    }

    fout << bestXor << ' ' << stBestXor << ' ' << drBestXor << '\n';
    return 0;
}