Cod sursa(job #2886210)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 7 aprilie 2022 12:29:55
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <string>
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;

};


string input;
int idx;
void Read(int& num)
{
    while (input[idx] < '0' || input[idx] > '9')
    {
        idx++;
    }

    num = 0;
    while (input[idx] >= '0' && input[idx] <= '9')
    {
        num = num * 10 + (input[idx] - '0');
        idx++;
    }
}

int main()
{
    getline(fin, input, char(0));
    Read(n);
    for (int i = 1; i <= n; i++)
    {
        int x;
        Read(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';

}