Pagini recente » Cod sursa (job #279588) | Cod sursa (job #2142850) | Cod sursa (job #1070280) | Cod sursa (job #2455317) | Cod sursa (job #1071630)
#include <iostream>
#include <fstream>
#define NMax 100010
#define start_level 21
#define bit (value & (1<<level)) != 0 ? 1 : 0
#define notbit (value & (1<<level)) != 0 ? 0 : 1
using namespace std;
int answer = -1, start, stop, result;
int sumxor[NMax];
int n, position_now, position_result;
struct Trie
{
int position;
Trie *fiu[2];
Trie()
{
position = 0;
for (int i=0; i<2; ++i)
fiu[i] = NULL;
}
};
Trie *T = new Trie();
inline void Add(Trie *nod, const int value, int level)
{
if (level == 0)
{
nod->position = position_now;
return ;
}
level--;
if (nod->fiu[bit] == 0)
nod->fiu[bit] = new Trie();
Add(nod->fiu[bit], value, level);
}
inline void query(const Trie *nod, const int value, int level)
{
if (level == 0)
{
position_result = nod->position;
return ;
}
level--;
if (nod->fiu[notbit])
{
result += (1<<level);
query(nod->fiu[notbit], value, level);
}
else
{
query (nod->fiu[bit], value, level);
}
}
int main()
{
ifstream f ("xormax.in");
f>>n;
position_now = 0;
Add(T, 0, start_level);
int i, number;
for (i=1; i<=n; ++i)
{
f>>number;
sumxor[i] = sumxor[i-1]^number;
result = 0;
query (T, sumxor[i], start_level);
if (result > answer)
{
answer = result;
start = position_result+1;
stop = i;
}
position_now = i;
Add(T, sumxor[i], start_level);
}
f.close();
ofstream g("xormax.out");
g<<answer<<" "<<start<<" "<<stop<<"\n";
g.close();
return 0;
}