Pagini recente » Cod sursa (job #1884652) | Cod sursa (job #24429) | Cod sursa (job #772006) | Monitorul de evaluare | Cod sursa (job #3348416)
#include <fstream>
#include <map>
using namespace std;
const int NMAX = 100000;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
struct trie{ ///exista sau nu doar la niv 21
trie *zero;
trie* unu;
trie() {
zero = NULL;
unu = NULL;
}
};
void add(trie* start, int nr, int bit) { ///bit sunt FIII
if(bit == -1)
return;
//cout << "suntem la " << (nr & (1 << bit)) << " la bitul " << bit << '\n';
if(nr & (1 << bit)) { ///unu
if(start->unu == NULL)
start->unu = new trie();
add(start->unu, nr, bit - 1);
}
else {
if(start->zero == NULL)
start->zero = new trie();
add(start->zero, nr, bit - 1);
}
}
int ans = 0;
void findd(trie* start, int nr, int bit) {
if(bit == -1) ///am terminat
return;
// cout << ans << " ";
// cout << "suntem la " << (nr & (1 << bit)) << " la bitul " << bit << '\n';
if(nr & (1 << bit)) { ///incercam sa gasim fara
if(start->zero == NULL) { ///nu exista, nasol
ans ^= (1 << bit);
findd(start->unu, nr, bit - 1);
}
else
findd(start->zero, nr, bit - 1);
}
else { ///incercam sa cautam cu
if(start->unu == NULL) {
//cout << "nu avem\n";
findd(start->zero, nr, bit - 1);
}
else {
ans ^= (1 << bit);
//cout << "avem\n";
findd(start->unu, nr, bit - 1);
}
}
}
int v[NMAX + 2];
map <int, int> umap; ///pt xor-uri
int main() {
trie *radacina = new trie();
int n;
cin >> n;
add(radacina, 0, 20); ///20 de biti actually
umap[0] = 0;
// ans = 1;
// findd(radacina, 1, 20);
// cout << ans;
// return 0;
int maxx = -1, st, dr;
for(int i = 1; i <= n; i++) {
int a;
cin >> a;
v[i] = (v[i - 1] ^ a);
// cout << v[i] << " ";
ans = v[i];
findd(radacina, v[i], 20);
// cout << ans << '\n';
if(ans > maxx) {
maxx = ans;
ans ^= v[i]; ///ca sa ii gasim partenerul
st = umap[ans] + 1;
dr = i;
}
// break;
if(umap.find(v[i]) == umap.end()) ///nici sa nu adaugam de mai multe ori
add(radacina, v[i], 20);
umap[v[i]] = i;
}
/*for(auto var : umap) {
cout << var.first << " " << var.second << '\n';
}*/
cout << maxx << " " << st << " " << dr;
return 0;
}