Pagini recente » Borderou de evaluare (job #872329) | Cod sursa (job #2045943)
#include <fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int aint[120000],a,pos,n,m,i;
void update(int st,int dr,int nod)
{
if(st==dr)
{
aint[nod]=a;
}
else
{
int mij=(st+dr)/2;
update(st,mij,nod*2);
update(mij+1,dr,nod*2+1);
aint[nod]=aint[2*nod]+aint[2*nod+1];
}
}
void update2(int st,int dr,int pos,int nod)
{
int mij=(st+dr)/2;
if(st==dr)
{
aint[nod]=0;
}
else if(mij>=pos)
{
update2(st,mij,pos,2*nod);
aint[nod]=aint[2*nod]+aint[2*nod+1];
}
else
{
update2(mij+1,dr,pos,2*nod+1);
aint[nod]=aint[2*nod]+aint[2*nod+1];
}
}
int query(int st,int dr,int p1,int nod)
{
int mij=(st+dr)/2;
if(st==dr)
{
update2(1,n,pos,1);
return st;
}
if(aint[2*nod]<p1)
{
return query(mij+1,dr,p1-aint[2*nod],2*nod+1);
}
else
{
return query(st,mij,p1,2*nod);
}
}
int main()
{
f>>n;
m=n;
a=1;
update(1,n,1);
pos=1;
for(i=1; i<=n; i++)
{
if(i+pos>=n)
{
pos=(i+pos)%m;
if(pos==0)
{
pos=m;
}
}
else
{
pos=i+pos;
}
g<<query(1,n,pos,1)<<" ";
m--;
}
return 0;
}