Nu aveti permisiuni pentru a descarca fisierul grader_test7.ok
Cod sursa(job #1510692)
| Utilizator | Data | 25 octombrie 2015 15:18:37 | |
|---|---|---|---|
| Problema | Xor Max | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 1.07 kb |
#include <iostream>
#include <cstdio>
using namespace std;
bool Trie[1 << 22];
int Map[1 << 21];
void add(int val)
{
int node=1, i;
for(i=20; i>=0; i--)
{
bool bit=(val>>i)&1;
Trie[node<<1 | bit]=1;
node=node<<1 | bit;
}
}
int xormax(int val)
{
int node=1, rez=0, i;
for(i=20; i>=0; i--)
{
bool bit=(val>>i)&1;
if(Trie[node<<1 | (bit^1)])
{
node=node<<1 | (bit^1);
rez=rez+(1<<i);
}
else node=node<<1 | bit;
}
return rez;
}
int main()
{
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
int n, sum=0, val, maxxor=-1, inc=-1, sf=-1, i, x;
scanf("%d", &n);
for(i=1; i<=n; i++)
{
Map[sum]=i;
add(sum);
scanf("%d", &val);
sum=sum^val;
x=xormax(sum);
if(x>maxxor)
{
maxxor=x;
sf=i;
inc=Map[sum^maxxor];
}
}
printf("%d %d %d", maxxor, inc, sf);
return 0;
}