Pagini recente » Cod sursa (job #2203681) | Cod sursa (job #428306) | Cod sursa (job #1690457) | Cod sursa (job #2128961) | Cod sursa (job #2886209)
#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';
}