Pagini recente » Cod sursa (job #2497493) | Cod sursa (job #2341918) | Cod sursa (job #765520) | Cod sursa (job #1144030) | Cod sursa (job #807211)
Cod sursa(job #807211)
#include <iostream>
#include <fstream>
using namespace std;
int i, s[100010], j, x, a, n, step, stop, maxstop, maxstart, maxim, sum;
bool t[30];
struct Trie{
Trie *fiu[2];
int poz;
Trie()
{
poz = 0;
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;
fi >> s[1];
for(i = 2; i <= n; i++)
{
fi >> a;
s[i] = s[i-1]^a;
}
for(i = n; i >= 1; i--)
{
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;
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;
}
}
adauga(T, 1);
}
for(i = 1; i <= n; i++)
if(s[i] > maxim or (s[i] == maxim and i == maxstop and maxstop-maxstart+1 > i) or (s[i] == maxim and i < maxstop))
{
maxim = s[i];
maxstop = i;
maxstart = 1;
}
fo << maxim << " " << maxstart << " " << maxstop << "\n";
return 0;
}