Pagini recente » Cod sursa (job #1091820) | Cod sursa (job #459665) | Cod sursa (job #216111) | Cod sursa (job #2773421) | Cod sursa (job #2885311)
#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';
}