Pagini recente » Cod sursa (job #2036161) | Cod sursa (job #1164796) | Cod sursa (job #3311605) | Cod sursa (job #571117) | Cod sursa (job #3309758)
#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
const int L = 31;
const int Nmax = 1e5 + 1;
int n, st, dr, x, v[Nmax];
struct Node
{
int fin = 0;
vector<Node*> sons;
Node():sons(2){}
~Node()
{
for(int i=0; i<2; i++)
if(this->sons[i] != nullptr)
delete this->sons[i];
}
};
Node* trie = nullptr;
Node* add(Node* p, const char* w, int idx)
{
if(p == nullptr)
p = new Node;
if(w[0] == '\0')
p->fin = idx; // salvăm indexul prefixului inserat
else
p->sons[w[0] - '0'] = add(p->sons[w[0] - '0'], w + 1, idx);
return p;
}
string s;
int query(Node* p, int pos)
{
if(pos < (int)s.size() && p != nullptr)
{
Node* bit1 = p->sons[1];
Node* bit0 = p->sons[0];
if(s[pos] == '0')
{
if(bit1 != nullptr)
return query(bit1, pos + 1);
else
return query(bit0, pos + 1);
}
else
{
if(bit0 != nullptr)
return query(bit0, pos + 1);
else
return query(bit1, pos + 1);
}
}
return p ? p->fin : 0;
}
static inline string make_key_from_pattern(string p)
{
reverse(p.begin(), p.end());
if((int)p.size() < L)
p.resize(L, '0');
return p;
}
int main()
{
int maxi = -1;
cin >> n;
v[0] = 0;
// inserează prefixul inițial 0 cu index 0
s.assign(L, '0');
trie = add(trie, s.c_str(), 0);
for(int i = 1; i <= n; i++)
{
cin >> x;
v[i] = v[i - 1] ^ x;
// construiește cheia binară pentru prefixul v[i]
s.clear();
int y = v[i];
if(y == 0) s.push_back('0');
while(y)
{
if(y & 1) s.push_back('1');
else s.push_back('0');
y >>= 1;
}
s = make_key_from_pattern(s);
int start = query(trie, 0);
if((v[i] ^ v[start]) > maxi)
{
maxi = v[i] ^ v[start];
st = start;
dr = i;
}
trie = add(trie, s.c_str(), i); // inserează prefixul curent cu indexul lui
}
cout << maxi << " " << st + 1 << " " << dr;
return 0;
}