Pagini recente » Cod sursa (job #619864) | Profil maritim | £ £ £ | Istoria paginii utilizator/ubb_anca_tutunaru_ungur | Cod sursa (job #1423751)
#include <fstream>
#include <utility>
#include <tuple>
using namespace std;
struct trie_nod{
~trie_nod(){
delete copii[0];
delete copii[1]; }
trie_nod* copii[2] = {nullptr, nullptr};
int val = 0; };
constexpr int sz = 21;
void adauga(trie_nod* t, const int n, const int val){
bool bit;
for(int adanc = sz; adanc >= 0; --adanc){
bit = (n & (1<<adanc))>>adanc;
if(t->copii[bit] == nullptr){
t->copii[bit] = new trie_nod; }
t = t->copii[bit]; }
t->val = val; }
tuple<int, int> cauta(trie_nod* t, const int n){
int rez = 0;
bool bit;
for(int adanc = sz, bit; adanc >= 0; --adanc){
bit = (n & (1<<adanc))>>adanc;
if(t->copii[bit] != nullptr){
t = t->copii[bit];
rez *= 2;
rez += bit; }
else{
t = t->copii[!bit];
rez *= 2;
rez += !bit; } }
return make_tuple(rez, t->val); }
int main(){
ifstream f("xormax.in");
int n = 0;
f >> n;
trie_nod* radacina = new trie_nod;
adauga(radacina, 0, 0);
int st_max = 0, dr_max = 0, val_max = -1, st_cur, val_cur;
for(int i = 0, x = 0, suma_partiala = 0; i < n; ++i){
f >> x;
suma_partiala ^= x;
adauga(radacina, suma_partiala, i+1);
tie(val_cur, st_cur) = cauta(radacina, ~suma_partiala);
val_cur ^= suma_partiala;
if(val_cur > val_max){
val_max = val_cur;
st_max = st_cur;
dr_max = i; }
else if(val_cur == val_max && i-st_cur < dr_max-st_max){
val_max = val_cur;
st_max = st_cur;
dr_max = i; } }
ofstream g("xormax.out");
g << val_max << ' ' << st_max+1 << ' ' << dr_max+1;
return 0; }