Cod sursa(job #2885251)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 5 aprilie 2022 19:10:10
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.9 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()
	
    {
	
        //memset(nodes, 0, sizeof(nodes));
	
        index = -1;
	
    }
	
 
	
    void Insert(vector <bool> bits, int inputIndex, int depth = 0)
	
    {
	
        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, depth + 1);
	
    }
	
 
	
    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 < 22)
	
    {
	
        bits.push_back(num % 2);
	
        num /= 2;
	
        index++;
	
    }
	
 
	
    return bits;
	
}
	
 
	
 
	
int main()
	
{
	
    fin >> n;
	
    for (int i = 1; i <= n; i++)
	
    {
	
        int x;
	
        fin >> 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';
	
}