Pagini recente » Cod sursa (job #2107315) | Cod sursa (job #2114502) | Cod sursa (job #2387598) | Cod sursa (job #2425187) | Cod sursa (job #2855259)
#include <bits/stdc++.h>
#define NMAX 100005
#define MAX_BITS 22
using namespace std;
/*******************************/
// INPUT / OUTPUT
ifstream f("xormax.in");
ofstream g("xormax.out");
/*******************************/
/// GLOBAL DECLARATIONS
int N;
int tempStart;
int 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();
/*******************************/
/// FUNCTIONS
void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
f >> N;
for (int i = 1 ; i <= N ; ++ i)
{
f >> v[i];
xorSum[i] = xorSum[i - 1] ^ v[i];
}
}
///-------------------------------------
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);
}
}
///-------------------------------------
inline void Output()
{
g << ans << " " << start << " " << stop;
}
///-------------------------------------
int main()
{
ReadInput();
Solution();
Output();
return 0;
}