Pagini recente » Cod sursa (job #2194409) | Cod sursa (job #287804) | Cod sursa (job #2272908) | Cod sursa (job #545642) | Cod sursa (job #429683)
Cod sursa(job #429683)
#include <fstream>
#define NMAX 100100
#define BMAX 23
using namespace std;
struct Trie
{
int L;
Trie* f[2];
Trie()
{
f[0] = f[1] = 0;
L = 0;
}
};
Trie* T;
int N, A[NMAX], best, bestI, bestJ, Sum[NMAX], j;
void readAll(void)
{
ifstream fin("xormax.in");
fin >>N;
for (int i = 1; i <= N; i++)
fin >>A[i];
fin.close();
}
void Cauta(Trie* T, int B, int Nr)
{
if (!T->f[0] && !T->f[1] ) {j = T->L; return;}
int x = 0;
if ( (1 << B) & Nr ) x = 1;
if ( T->f[1-x] ) Cauta(T->f[1-x], B-1, Nr);
else Cauta(T->f[x], B-1, Nr);
}
void Add(Trie* T, int B, int Nr, int Ind)
{
int x = 0;
if ( (1 << B) & Nr ) x = 1;
if (!T->f[x]) T->f[x] = new Trie;
if (B == 0) T->f[x]->L = Ind;
else Add(T->f[x], B - 1, Nr, Ind);
}
void Solve(void)
{
int i;
T = new Trie;
best = Sum[1];
bestI = 1;
bestJ = 0;
Add(T, BMAX, 0, 0);
for (i = 1; i <= N; i++)
{
Sum[i] = Sum[i-1] ^ A[i];
Cauta(T, BMAX, Sum[i]);
if ( (Sum[i] ^ Sum[j]) > best)
{
best = Sum[i] ^ Sum[j];
bestI = i;
bestJ = j;
}
Add(T, BMAX, Sum[i], i);
}
}
void writeAll(void)
{
ofstream fout("xormax.out");
fout <<best <<' '<<bestJ + 1 <<' '<<bestI <<'\n';
fout.close();
}
int main()
{
readAll();
Solve();
writeAll();
return 0;
}