Pagini recente » Cod sursa (job #3192171) | Cod sursa (job #935610) | Cod sursa (job #2461979) | Cod sursa (job #1868190) | Cod sursa (job #2944622)
#include<fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int n;
int aib[30001];
void upd(int poz, int val)
{
for(int i=poz;i<=n;i+=(i&(-i)))
aib[i]+=val;
}
int qry(int poz)
{
int rez=0;
for(int i=poz;i>0;i-=(i&(-i)))
rez+=aib[i];
return rez;
}
int query(int le, int ri)
{
if(le>ri)
return 0;
return qry(ri)-qry(le-1);
}
int verif(int inc, int mutari)
{
int sf;
sf=inc+mutari;
if(sf>n)
sf-=n;
if(sf==0)
sf=n;
if(inc<=sf)
return query(inc,sf);
else
return query(1,sf)+query(inc,n);
}
int main()
{
fin>>n;
int cur=1;
for(int i=1;i<=n;i++)
upd(i,1);
for(int i=1;i<=n;i++)
{
int st,dr,mij;
st=0;
dr=n;
cur++;
if(cur>n)
cur-=n;
int cate=i;
while(cate>(n-i+1))
{
cate-=(n-i+1);
}
while(st<=dr)
{
mij=(st+dr)/2;
if(verif(cur,mij)>=cate)
{
if(mij==0 || verif(cur,mij-1)<cate)
break;
else
dr=mij-1;
}
else
st=mij+1;
}
int sf=cur+mij;
if(sf>n)
sf-=n;
cur=sf;
upd(cur,-1);
fout<<cur<<" ";
}
return 0;
}
/**
1 2 3 4
2
3
1
2
*/