Cod sursa(job #917616)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 10:22:58
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
#define forv(i, v) for(size_t i = 0; i < (v).size(); i++)
#define forit(it, v) for(typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
typedef long double lod;
typedef long long lol;
typedef pair<int, int> pii;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct myt
{
int id;
myt *next[2];
myt()
{
memset(this->next, 0, sizeof(this->next)); this->id = 0;
}
};
myt *root = new myt;
int n, rd, bt, sum, sol = -1;
int s, f, iii;
int add_num, sol_num;
inline void add(myt *root, int bit)
{
if (bit == -1)
{
root->id = max(root->id, iii);
return ;
}
bt = ((add_num & (1 << bit)) > 0 ? 1 : 0);
if (root->next[bt] == 0)
root->next[bt] = new myt;
add(root->next[bt], bit - 1);
}
inline int take(myt *root, int bit)
{
if (bit == -1) return root->id;
bt = ((add_num & (1 << bit)) > 0 ? 0 : 1);
if (!(root->next[bt] == 0))
sol_num |= (1 << bit);
else bt = !bt;
return take(root->next[bt], bit - 1);
}
int main()
{
fin >> n;
add(root, 21);
for (iii = 1; iii <= n; iii++)
{
fin >> rd;
sum = sum ^ rd;
add_num = sum; sol_num = 0;
int var = take(root, 21);
add(root, 21);
if (sol < sol_num)
{
sol = sol_num;
s = var;
f = iii;
}
}
fout << sol << ' ' << s + 1 << ' ' << f; fout.close();
return 0;
}