Pagini recente » Cod sursa (job #626832) | Cod sursa (job #1996211) | Cod sursa (job #64648) | Cod sursa (job #3281487) | Cod sursa (job #3182184)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
int ind;
class Trie
{
int lvs = 0;
int cnt = 0;
int indice = 0;
Trie *next[2] = {};
public:
void Insert(string str , int ind , int pos = 0)
{
if(pos < str.size())
{
if(!next[str[pos] - '0'])
next[str[pos] - '0'] = new Trie;
next[str[pos] - '0']->Insert(str , ind , pos + 1);
if(pos == str.size() - 1)
indice = ind;
}
}
int Query (string str , int pos = 0 , int exp = 20)
{
if(!exp) {ind = indice;return 0;}
int bit = str[pos] - '0';
if(next[!bit])
return (1 << exp) + next[!bit]->Query(str , pos + 1 , exp - 1);
else if(next[bit])
return next[bit]->Query(str , pos + 1 , exp - 1);
else return 0;
}
}trie;
int N , X , ans , S;
int main()
{
int l , r;
fin >> N;
for(int i = 1; i <= N; ++i)
{
fin >> X;
S ^= X;
/// Convertesc suma in binar
stack <string> b;
string str = "";
int CS = S;
while(CS > 0)
{
if(CS % 2)
b.push("1");
else
b.push("0");
CS /= 2;
}
for(int j = 1; j <= 21 - (b.empty() ? 0 : b.size()); ++j)
str += "0";
while(!b.empty())
{
str += b.top();
b.pop();
}
int t = trie.Query(str);
if(t > ans)
ans = t , l = ind + 1, r = i;
trie.Insert(str , i);
}
fout << ans << " " << l << " " << r;
}