Pagini recente » Cod sursa (job #1896299) | Cod sursa (job #2860961) | Cod sursa (job #779699) | Cod sursa (job #2519449) | Cod sursa (job #469217)
Cod sursa(job #469217)
using namespace std;
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<cassert>
#include<bitset>
ofstream fout("xormax.out");
struct nod{
nod *son[2];
vector<int> sol;
nod()
{
memset(son,0,sizeof(son));
}
};
struct ptsol{
long long max,start,stop;
ptsol()
{max=start=stop=0;
}
};
ptsol curent,rasp;
typedef nod* trie;
int N;
long long a[100100],s[100100];
int sir[24];
trie R=new nod;
void ins(trie &n,int ind,int p)
{ if(p==23)
{
n->sol.push_back(ind);
return;
}
if(n->son[sir[p]]==NULL)
{
n->son[sir[p]]=new nod;
}
ins(n->son[sir[p]],ind,p+1);
}
/*void make(int p,int count)
{int cif;
if(count<=22)
{cif=s[p]%2;
s[p]/=2;
make(p,count+1);
sir[p][22-count+1]=cif;
}
}*/
inline void search(trie &n,int ind,int p)
{
if(p==23)
{int min=200000;
//cout<<ind<<":";
for(vector<int>::iterator it=n->sol.begin();it!=n->sol.end();++it)
{min=((min>(*it))&&(ind<(*it)))?*it:min;
// cout<<*it<<" ";
}
curent.stop=min;
curent.start=ind;
return;
}
if(n->son[sir[p]^1]==0)
{curent.max=curent.max*2+0;
search(n->son[sir[p]],ind,p+1);
}
else
{curent.max=curent.max*2+1;
search(n->son[(sir[p])^1],ind,p+1);
}
}
inline void solve()
{
for(int i=1;i<=N;i++)
{
bitset<23>muri(s[i]);
for(int j=0;j<=22;j++)
{sir[j]=muri[22-j];
}
ins(R,i,1);
}
cout<<"\n\n";
for(int i=1;i<=N;i++)
{ curent.max=0;
bitset<23>muri(s[i]);
for(int j=0;j<=22;j++)
{sir[j]=muri[22-j];
}
search(R,i,1);
if(a[i]>curent.max||(a[i]==curent.max&& i<=curent.stop))
curent.max=a[i],curent.stop=i,curent.start=i;
if(curent.max>rasp.max)
{rasp.max=curent.max;
rasp.stop=curent.stop;
rasp.start=curent.start;
}
else if(curent.max==rasp.max)
if(curent.stop<rasp.stop)
{rasp.stop=curent.stop;
rasp.start=curent.start;
}
else if(curent.stop==rasp.stop)
if(curent.stop-curent.start<rasp.stop-rasp.start)
rasp.start=curent.start;
}
fout<<rasp.max<<" "<<rasp.start+1<<" "<<rasp.stop<<"\n";
}
inline void sumation()
{
s[1]=a[1];
for(int i=1;i<=N;i++)
{s[i]=s[i-1]^a[i];
//cout<<s[i]<<" ";
}
// cout<<"\n";
}
inline void cit()
{
ifstream fin("xormax.in");
fin>>N;
for(int i=1;i<=N;i++)
fin>>a[i];
fin.close();
}
int main()
{
cit();
sumation();
solve();
//cout<<1;
fout.close();
return 0;
}