Cod sursa(job #2886209)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 7 aprilie 2022 12:27:05
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

int n;
int dp[100005];

class TrieNode

{

public:

    TrieNode()
    {
        nodes[0] = nodes[1] = nullptr;
        index = -1;
    }

    void Insert(int num,int inputIndex, int depth = 19)
    {
        if (depth == -1)
        {
            index = inputIndex;
            return;
        }

        int currBit = ((num >> depth) & 1);
        //cout << currBit;
        if (nodes[currBit] == nullptr)
        {
            nodes[currBit] = new TrieNode();
        }
        nodes[currBit]->Insert(num, inputIndex, depth - 1);
    }

    int DFS(int num, int depth = 19)
    {
        if (depth == -1)
        {
            return index;
        }

        int currBit = ((num >> depth) & 1);
        //cout << currBit;
        if (nodes[!currBit] != nullptr)
        {
            return nodes[!currBit]->DFS(num, depth - 1);
        }
        else
        {
            return nodes[currBit]->DFS(num, depth - 1);
        }
    }

private:
    TrieNode* nodes[2];
    int index;

};

int main()
{
    ios_base::sync_with_stdio(false);
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        fin >> x;
        dp[i] = dp[i - 1] ^ x;
    }

    TrieNode root = TrieNode();
    root.Insert(dp[1], 1);
    //cout << '\n';
    if (n == 1)
    {
        fout << dp[1] << ' ' << 1 << ' ' << 1 << '\n';
        return 0;
    }

    int maxValue = -1;
    int lfAns, rgAns;
    for (int i = 2; i <= n; i++)
    {
        int lfIndex = root.DFS(dp[i]);

        int posValue = dp[lfIndex] ^ dp[i];
        //cout << posValue << ' ' << lfIndex << ' ' << i << '\n';
        if (dp[i] > posValue && dp[i] > maxValue)
        {
            posValue = dp[i];
            lfAns = 1;
            rgAns = i;
        }
        else if (posValue > maxValue)
        {
            maxValue = posValue;
            lfAns = lfIndex + 1;
            rgAns = i;
        }

        root.Insert(dp[i], i);
        //cout << '\n';
    }

    fout << maxValue << ' ' << lfAns << ' ' << rgAns << '\n';

}