Pagini recente » Cod sursa (job #3284011) | Cod sursa (job #2806627) | Cod sursa (job #3004538) | Cod sursa (job #493421) | Cod sursa (job #3302110)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int NMAX = 1e5 + 1, BITMAX = 21;
int n, a[NMAX], prefix_xor[NMAX];
struct Node
{
int poz;
Node *children[2];
Node()
{
poz = -1;
children[0] = children[1] = nullptr;
}
};
Node *root = new Node();
void adauga(int val, int poz)
{
Node *node = root;
for(int i = BITMAX - 1; i >= 0; i--)
{
int bit = ((val >> i) & 1);
if(node->children[bit] == nullptr)
node->children[bit] = new Node();
node = node->children[bit];
}
node->poz = poz;
}
pair<int, int> query(int val)
{
int ans = 0;
Node *node = root;
for(int i = BITMAX - 1; i >= 0; i--)
{
int bit = ((val >> i) & 1);
if(node->children[1 - bit] != nullptr)
{
ans |= (1 << i);
node = node->children[1 - bit];
}
else
node = node->children[bit];
}
return {ans, node->poz};
}
int main()
{
fin >> n;
for(int i = 1; i <= n; i++)
{
fin >> a[i];
prefix_xor[i] = (prefix_xor[i - 1] ^ a[i]);
}
adauga(0, 0);
int vmax = -1, start = 1, finish = 1;
for(int j = 1; j <= n; j++)
{
auto [val, poz] = query(prefix_xor[j]);
if(val > vmax)
{
vmax = val;
start = poz + 1;
finish = j;
}
else if(val == vmax)
{
if(j < finish)
{
start = poz + 1;
finish = j;
}
else if(j == finish)
{
if((j - (poz + 1) + 1) < (finish - start + 1))
{
start = poz + 1;
finish = j;
}
}
}
adauga(prefix_xor[j], j);
}
fout << vmax << " " << start << " " << finish;
fin.close();
fout.close();
return 0;
}