Pagini recente » Cod sursa (job #2677125) | Cod sursa (job #2383285) | Cod sursa (job #3244654) | Cod sursa (job #539222) | Cod sursa (job #2623229)
#define MAX_N 100000
#define DELTA 21
#define INF 0x3f3f3f3f
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct trienode
{
trienode()
{
index = -1;
N[0] = N[1] = nullptr;
}
int index;
trienode* N[2];
} *root = new trienode;
int n, DP[MAX_N + 1];
int I = -1, J = -1, MA = -INF;
void TryUpdate(int value);
void Insert(int value);
void DeleteTrie(trienode* &node);
int main()
{
fin >> n;
for (int i = 1, x; i <= n; ++i)
{
fin >> x;
DP[i] = DP[i - 1] ^ x;
}
for (int i = 1; i <= n; ++i)
{
TryUpdate(i);
Insert(i);
}
fout << MA << ' ' << (I + 1) << ' ' << J;
DeleteTrie(root);
fin.close();
fout.close();
return 0;
}
int VALUE, INDEX, PARTNER;
void GetPartner(trienode* node, int index)
{
if (index == 1)
{
INDEX = node->index;
}
else
{
const bool bit = (VALUE >> (index - 1)) & 1;
if (node->N[!bit] != nullptr)
{
PARTNER |= (!bit) << (index - 1);
GetPartner(node->N[!bit], index - 1);
}
else
{
PARTNER |= bit << (index - 1);
GetPartner(node->N[bit], index - 1);
}
}
}
void TryUpdate(int index)
{
VALUE = DP[index];
PARTNER = 0;
INDEX = index;
if (root->N[0] != root->N[1])
{
GetPartner(root, DELTA - 1);
}
if (MA < (PARTNER ^ VALUE))
{
MA = PARTNER ^ VALUE;
I = INDEX;
J = index;
}
}
void InsertInNode(trienode* &node, int index)
{
if (node == nullptr)
{
node = new trienode;
}
if (index == 1)
{
node->index = INDEX;
}
else
{
const bool bit = (VALUE >> (index - 1)) & 1;
InsertInNode(node->N[bit], index - 1);
}
}
void Insert(int index)
{
VALUE = DP[index];
INDEX = index;
InsertInNode(root, DELTA - 1);
}
void DeleteTrie(trienode* &node)
{
if (node != nullptr)
{
DeleteTrie(node->N[0]);
DeleteTrie(node->N[1]);
delete node;
node = nullptr;
}
}