Pagini recente » Cod sursa (job #1975810) | Cod sursa (job #1149270) | Cod sursa (job #378130) | Cod sursa (job #2680551) | Cod sursa (job #2585176)
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
struct Trie
{
int pos;
Trie *fiu[2];
Trie()
{
pos = 0;
fiu[0] = fiu[1] = NULL;
}
};
Trie *t = new Trie;
int n, x, a[N], k;
int val, valPos;
int st = 1, dr = 1, ans;
int highestBit(int x)
{
int maxim = 0;
for (int i = 0; i < 21; i++)
if ((1 << i) & x)
maxim = i;
return maxim;
}
void Insert(Trie *p, int currK, int x, int ind)
{
if (currK == -1)
p -> pos = ind;
else
{
bool bit = 0;
if (x & (1 << currK))
bit = 1;
if (p -> fiu[bit] == NULL)
p -> fiu[bit] = new Trie;
Insert(p -> fiu[bit], currK - 1, x, ind);
}
}
void Search(Trie *p, int currK, int x)
{
if (currK == -1)
valPos = p -> pos;
else
{
bool bit = 0;
if (x & (1 << currK))
bit = 1;
if (p -> fiu[!bit] != NULL)
{
val ^= (1 << currK);
Search(p -> fiu[!bit], currK - 1, x);
}
else
Search(p -> fiu[bit], currK - 1, x);
}
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
fin >> x;
a[i] = (x ^ a[i - 1]);
k = max(k, highestBit(a[i]));
}
Insert(t, k, 0, 0);
for (int i = 1; i <= n; i++)
{
val = valPos = 0;
Search(t, k, a[i]);
if (val > ans)
{
ans = val;
st = valPos + 1;
dr = i;
}
Insert(t, k, a[i], i);
}
fout << ans << " " << st << " " << dr;
return 0;
}