Pagini recente » Cod sursa (job #2114388) | Cod sursa (job #93472) | Istoria paginii runda/onis-2014-runda-1/clasament | Cod sursa (job #78027) | Cod sursa (job #1881595)
#include <cstdio>
#define MAXN 200000
#define P2MAX 2097152
using namespace std;
struct Trie{
int pos;
Trie *son[2];
Trie(){
pos=0;
son[0]=son[1]=NULL;
}
};
Trie *t=new Trie;
int xorp[MAXN+1];
void add(Trie *node, int p2, int i){
if(p2==0){
node->pos=i;
return;
}
if(node->son[(xorp[i]&p2)>0]==NULL)
node->son[(xorp[i]&p2)>0]=new Trie;
add(node->son[(xorp[i]&p2)>0], p2>>1, i);
}
int maxxor(Trie *node, int p2, int i){
if(p2==0)
return node->pos;
if(node->son[1-((xorp[i]&p2)>0)]!=NULL)
return maxxor(node->son[1-((xorp[i]&p2)>0)], p2>>1, i);
return maxxor(node->son[(xorp[i]&p2)>0], p2>>1, i);
}
int main()
{
FILE *fin, *fout;
int n, maxim, maxst, maxdr, p, i;
fin=fopen("xormax.in", "r");
fscanf(fin, "%d", &n);
add(t, P2MAX, 0);
maxim=-1;
for(i=1; i<=n; i++){
fscanf(fin, "%d", &xorp[i]);
xorp[i]^=xorp[i-1];
p=maxxor(t, P2MAX, i);
if((xorp[i]^xorp[p])>maxim){
maxim=(xorp[i]^xorp[p]); maxst=p+1; maxdr=i;
}
add(t, P2MAX, i);
}
fclose(fin);
fout=fopen("xormax.out", "w");
fprintf(fout, "%d %d %d\n", maxim, maxst, maxdr);
fclose(fout);
return 0;
}