Pagini recente » Profil BadBoy | Istoria paginii utilizator/xsteffyz | Statistici Dobby Elf (dobby_is_free) | Cod sursa (job #941649) | Cod sursa (job #961714)
Cod sursa(job #961714)
#include<stdio.h>
#define NMAX 30000
int n,aib[NMAX+10];
void update (int pos, int val)
{
for(;pos<=n;pos=pos+(pos&-pos))
aib[pos]+=val;
}
int query (int pos)
{
int ans;
for(ans=0; pos; pos=pos-(pos&-pos))
ans+=aib[pos];
return ans;
}
int bs (int st, int dr, int val)
{
int med,qmed,last;
while(st<=dr)
{
med=(st+dr)/2;
qmed=query(med);
if(qmed==val)
last=med,
dr=med-1;
if(qmed<val)
st=med+1;
if(qmed>val)
dr=med-1;
}
return last;
}
int main()
{
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
int i,qn,qi,poz,caut,ramas;
scanf("%d",&n);
for(i=1;i<=n;i++)
update(i,1);
printf("2");
update(2,-1);
poz=2;
for(i=2;i<=n;i++)
{
qn=query(n);
qi=query(poz-1);
caut=i%qn;
if(!caut) caut=1;
if(caut<=qn-qi)
poz=bs(poz,n,qi+caut);
else
poz=bs(1,poz,caut-qn+qi);
update(poz,-1);
printf(" %d",poz);
}
printf("\n");
return 0;
}