Pagini recente » Cod sursa (job #2676183) | Cod sursa (job #1484820) | Cod sursa (job #966398) | Cod sursa (job #1701860) | Cod sursa (job #95280)
Cod sursa(job #95280)
#include <iostream>
#include <fstream>
using namespace std;
const int maxl = 22;
class nod
{
public:
nod(bool leaf);
~nod();
char* binValue;
int value;
int poz;
class nod *left;
class nod *rigth;
void setValue(int v);
};
nod::nod(bool leaf)
{
if(leaf)
{
binValue = new char[maxl];
for(int i=0;i<maxl;++i)
binValue[i] = 0;
}
else
{
binValue = 0;
}
left = 0;
rigth = 0;
}
nod::~nod()
{
if(binValue != 0 )
delete[] binValue;
if(left != 0 )
delete left;
if(rigth != 0 )
delete rigth;
}
void nod::setValue(int v)
{
value = v;
int poz = maxl - 1;
while(v > 0)
{
binValue[poz--] = v%2;
v /= 2;
}
}
void add(class nod *toNod, class nod *newNod, int level, bool left)
{
if(level == maxl-1)
{
if(left)
{
toNod->left = newNod;
}
else
toNod->rigth = newNod;
}
if(newNod->binValue[level] == 0)
{
if(toNod->left == 0)
{
class nod *leftNod = new nod(false);
toNod->left = leftNod;
}
add(toNod->left, newNod, level+1, true);
}
if(newNod->binValue[level] == 1)
{
if(toNod->rigth == 0)
{
class nod *rigthNod = new nod(false);
toNod->rigth = rigthNod;
}
add(toNod->rigth, newNod, level+1, false);
}
}
nod* getMax(class nod *fromNod, class nod *vNod, int level)
{
if(fromNod == 0)
return 0;
if(level == maxl-1)
{
if(vNod->binValue[level] == 0)
{
if(fromNod->rigth != 0)
return fromNod->rigth;
else
{
if(fromNod->left != 0)
return fromNod->left;
else
return 0;
}
}
if(vNod->binValue[level] == 1)
{
if(fromNod->left != 0)
return fromNod->left;
else
{
if(fromNod->rigth != 0)
return fromNod->rigth;
else
return 0;
}
}
}
if(vNod->binValue[level] == 0)
{
if(fromNod->rigth != 0)
return getMax(fromNod->rigth, vNod, level+1);
else
{
if(fromNod->left != 0)
return getMax(fromNod->left, vNod, level+1);
else
return 0;
}
}
if(vNod->binValue[level] == 1)
{
if(fromNod->left != 0)
return getMax(fromNod->left, vNod, level+1);
else
{
if(fromNod->rigth != 0)
return getMax(fromNod->rigth, vNod, level+1);
else
return 0;
}
}
}
int main(void)
{
ifstream in;
ofstream out;
in.open("xormax.in");
out.open("xormax.out");
int n;
in >> n;
int xorV = 0;
int maxV = 0;
int s = 0;
int e = 0;
class nod* tree = new nod(false);
for(int i=0;i<n;++i)
{
int d;
in >> d;
xorV = xorV ^ d;
if(d > maxV)
{
maxV = d;
s = i;
e = i;
}
class nod *n = new nod(true);
n->setValue(xorV);
n->poz = i;
class nod* maxValue = getMax(tree, n, 0);
if(maxValue != 0)
{
int tmpV = maxValue->value ^ xorV;
if(tmpV > maxV)
{
maxV = tmpV;
s = maxValue->poz+1;
e = i;
}
}
add(tree, n, 0, true);
}
in.close();
out << maxV << " " << s+1 << " " << e+1 << endl;
out.close();
// delete tree;
return 0;
}