Pagini recente » Cod sursa (job #2457413) | Cod sursa (job #2039640) | Cod sursa (job #1226979) | Cod sursa (job #1177150) | Cod sursa (job #2885206)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n;
int v[100005];
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();
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 < 20)
{
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;
v[i] = x;
dp[i] = dp[i - 1] ^ x;
}
TrieNode root = TrieNode();
vector <bool> currBits = GetBits(dp[1]);
root.Insert(currBits, 1);
int maxValue = -1;
int lfAns, rgAns;
for (int i = 2; i <= n; i++)
{
currBits = GetBits(dp[i]);
int lfIndex = root.DFS(currBits);
int posValue = v[lfIndex] ^ v[i];
if (posValue > maxValue)
{
maxValue = posValue;
lfAns = lfIndex;
rgAns = i;
}
root.Insert(currBits, i);
}
fout << maxValue << ' ' << lfAns << ' ' << rgAns << '\n';
}