Pagini recente » Cod sursa (job #2662209) | Cod sursa (job #2872546)
#include <fstream>
#define NMAX 100005
#define MAX_BITS 22
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int N, tempStart, ans, start = 1, stop = 1;
char bitSet[MAX_BITS];
int v[NMAX], xorSum[NMAX];
struct Trie
{
int freq, start;
Trie *fii[2];
};
Trie *trie = new Trie();
void Add(Trie *pos, char *bits)
{
pos->freq ++;
if (*bits == '\0')
{
pos->start = tempStart;
return;
}
int bit = *bits - '0';
if (pos->fii[bit] == NULL)
{
pos->fii[bit] = new Trie();
}
Add(pos->fii[bit], bits + 1);
}
///-------------------------------------
int FindXor(Trie *pos, char *bits)
{
if (*bits == '\0')
{
return pos->start;
}
int bit = *bits - '0';
int otherBit = (bit + 1) % 2;
if (pos->fii[otherBit] != NULL)
{
return FindXor(pos->fii[otherBit], bits + 1);
}
else
{
return FindXor(pos->fii[bit], bits + 1);
}
}
///-------------------------------------
void ToBinary(int num)
{
int bitNum = 0;
while (num)
{
bitSet[bitNum ++] = num % 2 + '0';
num /= 2;
}
for (int i = 0 ; i < bitNum / 2 ; ++ i)
{
swap(bitSet[i], bitSet[bitNum - i - 1]);
}
int cnt = 1;
for (int i = bitNum - 1 ; i >= 0 ; -- i)
{
bitSet[MAX_BITS - cnt] = bitSet[i];
cnt ++;
}
for (int i = 0 ; i < MAX_BITS - bitNum ; ++ i)
{
bitSet[i] = '0';
}
}
///-------------------------------------
inline void Solution()
{
ToBinary(0);
Add(trie, bitSet);
for (int i = 1 ; i <= N ; ++ i)
{
ToBinary(xorSum[i]);
int foundStart = FindXor(trie, bitSet);
int tempXor = xorSum[i] ^ xorSum[foundStart];
if (ans < tempXor)
{
ans = tempXor;
if (foundStart == 0) start = i;
else start = foundStart + 1;
stop = i;
}
tempStart = i;
Add(trie, bitSet);
}
}
int main()
{
cin >> N;
for (int i = 1 ; i <= N ; ++ i)
{
cin >> v[i];
xorSum[i] = xorSum[i - 1] ^ v[i];
}
Solution();
cout << ans << ' ' << start << ' ' << stop << '\n';
}