Pagini recente » Cod sursa (job #3233004) | Cod sursa (job #2441584) | Cod sursa (job #257194) | Cod sursa (job #2373422) | Cod sursa (job #773523)
Cod sursa(job #773523)
#include<fstream>
#define lsb(x) (x&(-x))
using namespace std;
int n,i,aib[30003],x,rez,j,ld,qn;
void update(int poz,int val)
{int i;
for(i=poz;i<=n;i+=lsb(i))
aib[i]+=val;
}
int query(int poz)
{int i,s=0;
for(i=poz;i>=1;i-=lsb(i))
s+=aib[i];
return s;
}
int bs(int nr)
{int mij,s=1,d=n,val;
while(s<=d)
{
mij=(s+d)/2;
val=query(mij);
if(val<nr)s=mij+1;
if(val>nr)d=mij-1;
if(val==nr){ rez=mij; d=mij-1; }
}
return rez;
}
int main()
{
ifstream f("order.in");ofstream g("order.out");
f>>n;
for(i=1;i<=n;i++)
update(i,1);
rez=1;
for(i=1;i<=n;i++)
{
x=rez;
qn=query(n);
ld=qn-query(rez);
if(ld<i)
{
x=i-ld;
x=x%qn;
if(x==0)x=qn;
rez=bs(x);
}
else rez=bs(query(x)+i);
g<<rez<<' ';
update(rez,-1);
}
f.close();g.close();
return 0;}