Pagini recente » Cod sursa (job #2987243) | Cod sursa (job #2814706) | Cod sursa (job #2944180) | Cod sursa (job #2814368) | Cod sursa (job #2704358)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int N = 23;
int n, x, sum, m, Bin[N], k = N - 2, ans, start, Max, l, r;
struct Trie
{
int BestPos = 0;
Trie *next[2] = {};
};
Trie *root = new Trie;
void GetBinary(int x)
{
m = 0;
while (x)
{
m++;
Bin[m] = x % 2;
x /= 2;
}
for (int i = m + 1; i <= k; i++)
Bin[i] = 0;
}
void AddValue(Trie *key, int pos, int crt)
{
if (!pos)
{
if (crt > (key->BestPos))
key->BestPos = crt;
return;
}
int p = Bin[pos];
if (key->next[p] == NULL)
key->next[p] = new Trie;
AddValue(key->next[p], pos - 1, crt);
}
void SearchValue(Trie *key, int pos)
{
if (!pos)
{
start = key->BestPos;
return;
}
int nextValue = Bin[pos];
if (!nextValue)
nextValue = 1;
else
nextValue = 0;
ans = ans * 2;
if (key->next[nextValue] != NULL)
{
ans++;
SearchValue(key->next[nextValue], pos - 1);
}
else
SearchValue(key->next[Bin[pos]], pos - 1);
}
int main()
{
fin >> n;
Max = v[1];
for (int i = 1; i <= n; i++)
{
fin >> x;
sum ^= x;
GetBinary(sum);
if (i > 1)
{
ans = 0;
SearchValue(root, k);
if (ans > Max)
{
Max = ans;
l = start + 1;
r = i;
}
}
AddValue(root, k, i);
}
fout << Max << " " << l << " " << r << '\n';
}