Pagini recente » Cod sursa (job #2444835) | Cod sursa (job #2732667) | Cod sursa (job #2442700) | Cod sursa (job #1356706) | Cod sursa (job #2300115)
#include <fstream>
using namespace std;
class node
{
public:
int pos;
node* v[2];
node()
{
this->pos = 0;
this->v[0] = this->v[1] = NULL;
}
~node()
{
if (this->v[0] != NULL)
delete this->v[0];
if (this->v[1] != NULL)
delete this->v[1];
}
};
class trie
{
public:
trie()
{
root = new node();
}
~trie()
{
delete root;
}
int Query(const int &x)
{
return RecursiveQuery(root, x, 20);
}
void Add(const int &x, const int &pos)
{
RecursiveAdd(root, x, 20, pos);
}
private:
int RecursiveQuery(node* currNode, const int &val, int bitPos)
{
if (bitPos == -1)
return currNode->pos;
if (currNode->v[1 - (((1 << bitPos) & val) > 0)] != NULL)
return RecursiveQuery(currNode->v[1 - (((1 << bitPos) & val) > 0)], val, bitPos - 1);
else
return RecursiveQuery(currNode->v[(((1 << bitPos) & val) > 0)], val, bitPos - 1);
}
void RecursiveAdd(node* currNode, const int &val, int bitPos, const int &valPos)
{
if (bitPos == -1)
{
currNode->pos = valPos;
return;
}
if (currNode->v[(((1 << bitPos) & val) > 0)] == NULL)
currNode->v[(((1 << bitPos) & val) > 0)] = new node();
RecursiveAdd(currNode->v[(((1 << bitPos) & val) > 0)], val, bitPos - 1, valPos);
}
node *root;
};
const int NMAX = 1e5 + 5;
int n, s[NMAX];
trie T;
int main()
{
ifstream fin("xormax.in");
ofstream fout("xormax.out");
int stg = 0, drp = 0, valMax = -1;
fin >> n;
for (int i = 1;i <= n;++i)
{
fin >> s[i];
s[i] ^= s[i - 1];
}
T.Add(0, 0);
for (int i = 1;i <= n;++i)
{
int aux = T.Query(s[i]);
if ((s[i] ^ s[aux]) > valMax)
{
stg = aux + 1;
drp = i;
valMax = s[i] ^ s[aux];
}
T.Add(s[i], i);
}
fout << valMax << " " << stg << " " << drp << "\n";
fin.close();
fout.close();
return 0;
}