Pagini recente » Cod sursa (job #409636) | Cod sursa (job #1999686) | Cod sursa (job #2252068) | Cod sursa (job #2472932) | Cod sursa (job #848667)
Cod sursa(job #848667)
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
struct trie{
trie *sons[2];
vector <int> ind;
trie(){
memset(sons,0,sizeof(sons));
}
};
trie *root = new trie;
int mx,ind1,ind2,v[100001], xloc[100001],crit;
void trad(trie *tra, vector<int>v, int it) {
if (it==v.size())
tra->ind.push_back(crit);
else {
if (tra->sons[v[it]] == 0)
tra->sons[v[it]] = new trie;
trad(tra->sons[v[it]],v,it+1);
}
}
void bitty(int x) {
vector <int> v;
vector <int> w;
int i;
while (x) {
v.push_back(x%2);
x/=2;
}
for (i=1;i<=(20-v.size()); i++)
w.push_back(0);
for (i=v.size()-1; i>=0; i--)
w.push_back(v[i]);
trad(root, w, 0);
}
int xar(trie *tra, vector <int> v, int it) {
if (it==v.size())
return tra->ind[0];
else {
if (tra->sons[v[it]])
return xar(tra->sons[v[it]],v,it+1);
else
return xar(tra->sons[!v[it]],v,it+1);
}
}
void sear(int x) {
vector <int> v;
vector <int> w;
int i;
while (x) {
v.push_back(!(x%2));
x/=2;
}
for (i=1; i<=(20-v.size()); i++)
w.push_back(1);
for (i=v.size()-1; i>=0; i--)
w.push_back(v[i]);
int l = xar(root,w,0);
if (xloc[crit]^xloc[l]>mx) {
mx = xloc[crit]^xloc[l];
ind1 = l+1;
ind2 = crit;
}
}
int main() {
int n,i,j,k;
ifstream in("xormax.in");
ofstream out("xormax.out");
mx = -1;
in>>n;
in>>v[1];
xloc[1] = v[1];
bitty(v[1]);
for (i=2; i<=n; i++) {
in>>v[i];
xloc[i]=xloc[i-1]^v[i];
crit = i;
sear(xloc[i]);
bitty(xloc[i]);
}
out<<mx<<' '<<ind1<<' '<<ind2<<'\n';
out.close();
return 0;
}