Pagini recente » Cod sursa (job #313831) | Cod sursa (job #2843949) | Cod sursa (job #2418345) | Cod sursa (job #1529068) | Cod sursa (job #692891)
Cod sursa(job #692891)
#include <fstream>
#include <algorithm>
#define lim 22
#define MAX 100050
using namespace std;
int v[MAX], sumaXOR[MAX], maxim = -1, start, end, n;
struct Trie
{
int inf;
Trie *st, *dr;
Trie()
{
inf = 0;
st = dr = 0;
}
}*T = new Trie;
inline void add(Trie *nod, int poz, int x)
{
int i, bit;
for(i = lim; i >= 0; i--)
{
bit = (x & (1 << i));
if(bit)
{
if(!nod->st)
nod->st = new Trie;
nod = nod->st;
}
else
{
if(!nod->dr)
nod->dr = new Trie;
nod = nod->dr;
}
}
nod->inf = poz;
}
inline int lookAfter(Trie *nod, int x)
{
int i, bit;
for(i = lim; i >= 0; i--)
{
bit = (x & (1 << i));
if(bit)
{
if(nod->dr)
nod = nod->dr;
else
nod = nod->st;
}
else
{
if(nod->st)
nod = nod->st;
else
nod = nod->dr;
}
}
return nod->inf;
}
int main()
{
int i,j;
ifstream fin("xormax.in");
fin>>n;
add(T, 0, 0);
for(i=1; i<=n; i++)
{
fin>>v[i];
sumaXOR[i]=(sumaXOR[i-1]^v[i]);
j=lookAfter(T,sumaXOR[i]);
if(maxim<(sumaXOR[j]^sumaXOR[i]))
{
maxim=(sumaXOR[j]^sumaXOR[i]);
start = j;
end = i;
}
add(T,i, sumaXOR[i]);
}
fin.close();
ofstream fout("xormax.out");
fout<<maxim<<' '<<(start+1)<<' '<<end<<"\n";
fout.close();
return 0;
}