Pagini recente » Cod sursa (job #2616890) | Cod sursa (job #2131433) | Cod sursa (job #1826796) | Cod sursa (job #2918559) | Cod sursa (job #2923258)
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int n, xor_partial[100005];
class TrieNode
{
TrieNode *edges[2];
int index;
public:
TrieNode()
{
edges[0] = edges[1] = nullptr;
index = -1;
}
void Insert(int num, int inputIndex, int depth)
{
if (depth == -1)
{
index = inputIndex;
return;
}
int curentBit = ((num >> depth) & 1);
if (edges[curentBit] == nullptr)
{
edges[curentBit] = new TrieNode();
}
edges[curentBit]->Insert(num, inputIndex, depth - 1);
}
int DFS(int num, int depth = 19)
{
if (depth == -1)
{
return index;
}
int curentBit = ((num >> depth) & 1);
if (edges[!curentBit] != nullptr)
{
return edges[!curentBit]->DFS(num, depth - 1);
}
else
{
return edges[curentBit]->DFS(num, depth - 1);
}
}
};
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
int x;
fin >> x;
xor_partial[i] = xor_partial[i - 1] ^ x;
}
TrieNode root = TrieNode();
root.Insert(xor_partial[1], 1, 19);
if (n == 1)
{
fout << xor_partial[1] << "1 1\n";
return 0;
}
int maxValue = -1;
int leftAns, rightAns;
for (int i = 2; i <= n; i++)
{
int left = root.DFS(xor_partial[i]);
int valPosibil = xor_partial[left] ^ xor_partial[i];
if (xor_partial[i] > valPosibil && xor_partial[i] > maxValue)
{
valPosibil = xor_partial[i];
leftAns = 1;
rightAns = i;
}
else if (valPosibil > maxValue)
{
maxValue = valPosibil;
leftAns = left + 1;
rightAns = i;
}
root.Insert(xor_partial[i], i, 19);
}
fout << maxValue << ' ' << leftAns << ' ' << rightAns << '\n';
return 0;
}