Pagini recente » Cod sursa (job #2716280) | Cod sursa (job #2519374) | Cod sursa (job #785607) | Cod sursa (job #2884293) | Cod sursa (job #2660736)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("xormax.in");
ofstream cout("xormax.out");
int p[23],n,v[100001],maxi,y,z1,z2,nr;
bool s[23];
struct Trie {
Trie *Bit[26];
int prefix,cuv,numar;
Trie(){
for(short int i=0;i<26;i++)
Bit[i]=nullptr;
prefix=0;
cuv=0;
}
};
Trie *rad =new Trie();
void ADD(Trie *&nod, int i, int dr) {
if (i == 22) {
nod -> numar = dr;
return;
}
if(nod -> Bit[s[i]] == NULL) {
nod -> Bit[s[i]] = new Trie;
}
ADD(nod -> Bit[s[i]], i + 1,dr);
return;
}
void REMOVE( char *x){
Trie *aux=rad;
for(short int i=0;i<strlen(x);i++){
if(aux->Bit[x[i]-'a']==nullptr) {
return;
}
aux->Bit[x[i]-'a']->prefix--;
aux=aux->Bit[x[i]-'a'];
}
aux->cuv--;
}
void CHANGE(int x) {
int k = -1;
for (int i = 0; i <= 21; i ++) {
s[i] = 0;
}
while (x > 0) {
s[++k] = x % 2;
x /= 2;
}
for (int i = 0; i <= 10; i ++) {
swap (s[i],s[21-i]);
}
return;
}
int dfs(Trie *&nod,int i) {
if (i==22) {
y=nod->numar;
return 0;
}
if (nod->Bit[1-s[i]]!=NULL) {
return p[(21-i)]+dfs(nod->Bit[1-s[i]],i+1);
}
else {
return dfs(nod->Bit[s[i]],i+1);
}
}
int main (void) {
cin>>n;
for(int i=1;i<=n;i++) {
cin>>v[i];
}
for(int i=1;i<=n;i++) {
v[i]=(v[i] ^ v[i-1]);
}
p[0]=1;
for(int i=1;i<=22;i++) {
p[i]=p[i-1]*2;
}
maxi=-1;
CHANGE(0);
ADD(rad,0,0);
for(int i=1;i<=n;i++) {
CHANGE(v[i]);
nr=dfs(rad,0);
if(nr>maxi) {
maxi=nr;
z1=i;
z2=y;
}
ADD(rad,0,i);
}
cout<<maxi<<" "<<z2+1<<" "<<z1<<" ";
return 0;
}