Pagini recente » Cod sursa (job #245214) | Cod sursa (job #2109261) | Cod sursa (job #97495) | Cod sursa (job #1315860) | Cod sursa (job #2950593)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("xormax.in");
ofstream out ("xormax.out");
/**
punem fiecare prefix de xor (a[1] ^ a[2] ^ ... ^ a[i])
daca ne aflam pe pozitia j
sa gasim un prefix astfel incat
(a[1] ^ a[2] ^ ... ^ a[j]) ^ (a[1] ^ a[2] ^ ... ^ a[i]) este maxim
= a[i+1] ^ a[i+2] ^ ... ^ a[j]
=> problema se reduce la a gasi valoarea maxima a xor dintre doua valori dintr un vector <=>
pentru fiecare index j gasim valoarea maxima astfel incat
(a[1] ^ a[2] ^ ... ^ a[j]) ^ (a[1] ^ a[2] ^ ... ^ a[i]) este maxim
**/
#define int long long
struct node
{
int x;
int start;
node *f[2];
};
node *newnode (int pos)
{
node *temp = new node;
temp -> x = 0;
temp -> f[0] = temp -> f[1] = NULL;
temp -> start = pos;
return temp;
}
void insert (node *root, int curr, int pos)
{
node *temp = root;
for (int i=21; i>=0; i--)
{
bool val = curr & (1LL << i);
if (temp -> f[val] == NULL)
temp -> f[val] = newnode(pos);
temp = temp -> f[val];
}
temp -> start = pos;
temp -> x = curr;
}
pair<int, int> query (node *root, int curr)
{
node *temp = root;
for (int i=21; i>=0; i--)
{
bool val = curr & (1LL << i);
if (temp -> f[(val ^ 1)] != NULL)
temp = temp -> f[(val ^ 1)];
else if (temp -> f[val] != NULL)
temp = temp -> f[val];
else
break;
}
return {curr ^ (temp -> x), temp -> start + 1};
}
signed main()
{
int n;
in >> n;
node *root = newnode(1);
insert(root, 0, 0);
int ans = -1, curr = 0;
int start = -1, stop = n + 1;
for (int i=1; i<=n; i++)
{
int x;
in >> x;
curr ^= x;
insert(root, curr, i);
pair<int, int> res = query(root, curr);
if (res.second > i)
res.second--;
//out << res.first << ' ' << res.second << '\n';
if (res.first > ans)
{
ans = res.first;
start = res.second;
stop = i;
}
else if (res.first == ans)
{
if (i - res.second + 1 < stop - start + 1)
{
start = res.second;
stop = i;
}
}
}
out << ans << ' ' << start << ' ' << stop;
return 0;
}