Pagini recente » Cod sursa (job #1045265) | Cod sursa (job #2366366) | Cod sursa (job #1223599) | Cod sursa (job #2717770) | Cod sursa (job #1922036)
#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, 22, 0, 0);
for(i = 1; i <= n; i++)
{
fin >> x;
sum[i] = sum[i - 1] ^ x;
//fout << sum[i] << " ";
int nr = sum[i];
//fout << sum[i] <<"\n";
adauga(root, 22, nr, i);
//fout<<"\n";
int maxim = 0;
int aux = cauta(root, 22, sum[i], maxim);
if(maxim > sol)
{
sol = maxim;
st = aux + 1;
dr = i;
}
else
{
//if(maxim == sol)
}
//fout << maxim <"\n";
/*fout<<nr<<"\n";
string sir;
while(nr)
{
//fout << nr % 2<<" ";
int modulo = nr % 2;
sir = (char)(modulo + '0') + sir;
nr = nr / 2;
}
fout<<sir;
fout<<"\n";*/
}
fout << sol <<" "<<st<<" "<<dr<<"\n";
}