Cod sursa(job #2885311)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 5 aprilie 2022 19:51:44
Problema Xor Max Scor 15
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.83 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(vector <bool> bits, int inputIndex)
    {
        if (bits.empty())
        {
            index = inputIndex;
            return;
        }

        int currBit = bits.back();
        bits.pop_back();
        //cout << currBit;
        if (nodes[currBit] == nullptr)
        {
            nodes[currBit] = new TrieNode();
        }

        nodes[currBit]->Insert(bits, inputIndex);
    }

    int DFS(vector <bool> bits)
    {
        if (bits.empty())
        {
            return index;
        }

        int currBit = bits.back();
        bits.pop_back();
        
        if (nodes[!currBit] != nullptr)
        {
            return nodes[!currBit]->DFS(bits);
        }
        else
        {
            return nodes[currBit]->DFS(bits);
        }
    }

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


vector <bool> GetBits(int num)
{
    vector <bool> bits;
    int index = 0;

    while (index < 20)
    {
        bits.push_back(num % 2);
        num /= 2;
        index++;
    }

    return bits;
}

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()
{
    ios_base::sync_with_stdio(false);
    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();

    vector <bool> currBits = GetBits(dp[1]);
    root.Insert(currBits, 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++)
    {
        //currBits = GetBits(dp[i]);
        int lfIndex = root.DFS(currBits);

        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(currBits, i);
        //cout << '\n';
    }

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