Pagini recente » Cod sursa (job #2600455) | Cod sursa (job #1993230) | Cod sursa (job #3227212) | Cod sursa (job #568718) | Cod sursa (job #1922097)
#include<fstream>
#include<vector>
#include<string>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
string sir;
int i, n, k, j,contor,st,dr,sol,x,y,c;
int sum[100005];
struct Node
{
int index;
Node *urm[2];
Node()
{
//fout << "ajunge"<<"\n";
for(int i = 0; i < 2; i++)
{
urm[i] = NULL;
}
}
};
void adauga(Node *node, int pos, int nr, int i)
{
if(pos == -1)
{
//fout<<"final\n";
//cuvantul i se termina pe acest nod din trie
node->index = i;
return;
}
//selectam bitul de pe pozitia poz
int bit = (1 << pos) & nr ? 1 : 0;
//fout << bit << " ";
if(node->urm[bit] == NULL)
{
node->urm[bit] = new Node();
}
adauga(node->urm[bit], pos - 1, nr, i);
}
int cauta(Node *node, int pos, int nr, int &maxim)
{
if(pos == -1)
{
return node->index;
}
int bit = ((1 << pos) & nr ? 0 : 1);
if(node->urm[bit] != NULL)
{
maxim = (1 << pos) ^ maxim;
}
else
{
bit = (bit ? 0 : 1);
}
return cauta(node->urm[bit], pos - 1, nr, maxim);
}
int main()
{
Node *root = new Node();
fin >> n;
//adauga(root, 20, 0, 0);
for(i = 1; i <= n; i++)
{
fin >> x;
sum[i] = sum[i - 1] ^ x;
//fout << sum[i] << " ";
int nr = sum[i];
adauga(root, 20, nr, i);
int maxim = 0;
int aux = cauta(root, 20, sum[i], maxim);
if(maxim > sol)
{
sol = maxim;
st = aux + 1;
dr = i;
}
//fout << maxim <"\n";
}
fout << sol <<" "<<st<<" "<<dr<<"\n";
}