Pagini recente » Cod sursa (job #2606188) | Cod sursa (job #630785) | Cod sursa (job #1476173) | Cod sursa (job #1313104) | Cod sursa (job #807190)
Cod sursa(job #807190)
#include <iostream>
#include <fstream>
using namespace std;
int i, s[100010], j, x, a[100010], n, step, stop, maxstop, maxstart, maxim, sum;
bool t[30];
struct Trie{
Trie *fiu[2];
int poz;
Trie()
{
fiu[0] = fiu[1] = 0;
}
};
Trie *T = new Trie;
void adauga(Trie *node, int p)
{
if(p > 21)
{
if(!node->poz) node->poz = i;
return;
}
if(!node->fiu[t[p]])
node->fiu[t[p]] = new Trie();
adauga(node->fiu[t[p]], p+1);
}
int get_max(Trie *node, int p, int bit)
{
if(p > 21)
{
stop = node->poz;
return 0;
}
if(node->fiu[1-t[p]])
return get_max(node->fiu[1-t[p]], p+1, bit >> 1)+bit;
else
return get_max(node->fiu[t[p]], p+1, bit >> 1);
}
int main()
{
ifstream fi("xormax.in");
ofstream fo("xormax.out");
fi >> n;
for(i = 1; i <= n; i++) fi >> a[i];
s[1] = a[1];
for(i = 2; i <= n; i++) s[i] = s[i-1]^a[i];
for(i = n; i >= 1; i--)
{
//construiesc sirul binar
for(step = 1, j = 1; j <= 20; j++, step <<= 1);
for(j = 1; j <= 21; step >>= 1, j++)
if(step&s[i]) t[j] = 1; else t[j] = 0;
//incerc sa-l gasesc maximul in trie
for(step = 1, j = 1; j <= 20; j++, step <<= 1);
if(i != n)
{
sum = get_max(T, 1, step);
if(sum > maxim or (sum == maxim and stop < maxstop))
{
maxim = sum;
maxstop = stop;
maxstart = i+1;
}
}
//adaug i la trie
adauga(T, 1);
}
for(i = 1; i <= n; i++)
if(s[i] > maxim or (s[i] == maxim and i < maxstop))
{
maxim = s[i];
maxstop = i;
maxstart = 1;
}
fo << maxim << " " << maxstart << " " << maxstop << "\n";
return 0;
}