Pagini recente » Monitorul de evaluare | Cod sursa (job #972285) | Cod sursa (job #3239448) | Cod sursa (job #839935) | Cod sursa (job #3324912)
#include <fstream>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
struct Trie
{
int val, pos;
Trie *next[2];
Trie(): val(0), pos(0)
{
next[0] = next[1] = NULL;
}
} *root, *crt, *sol;
int n, x, l, r, sum, maxSum;
void Insert(int val, int pos)
{
crt = root;
for (int bit = 21; bit >= 0; bit--)
{
bool id = ((val >> bit) & 1);
if (crt->next[id] == NULL)
crt->next[id] = new Trie;
crt = crt->next[id];
}
crt->val = val;
crt->pos = pos;
}
Trie* FindPrefix(int val)
{
crt = root;
for (int bit = 21; bit >= 0; bit--)
{
bool id = ((val >> bit) & 1);
if (crt->next[id ^ 1] != NULL)
crt = crt->next[id ^ 1];
else
crt = crt->next[id];
}
return crt;
}
int main()
{
root = new Trie;
l = r = 0;
maxSum = -1;
sum = 0;
///
f >> n;
for (int i = 1; i <= n; i++)
{
f >> x;
Insert(sum, i - 1);
sum ^= x;
sol = FindPrefix(sum);
if ((sol->val ^ sum) > maxSum)
{
maxSum = (sol->val ^ sum);
l = sol->pos + 1;
r = i;
}
}
///
g << maxSum << ' ' << l << ' ' << r;
f.close();
g.close();
return 0;
}