Pagini recente » Cod sursa (job #968541) | Cod sursa (job #1567725) | Cod sursa (job #1590133) | Cod sursa (job #1697678) | Cod sursa (job #787366)
Cod sursa(job #787366)
#include<fstream>
using namespace std;
int n,aib[30100];
inline void Update(int poz,int val)
{
while(poz<=n)
{
aib[poz]+=val;
poz+=(poz & -poz);
}
}
inline int Query(int poz)
{
int sum=0;
while(poz>0)
{
sum+=aib[poz];
poz-=(poz & -poz);
}
return sum;
}
inline int CautareBinara(int val)
{
int st,dr,mij,x,rez;
st=1;
dr=n;
while(st<=dr)
{
mij=(st+dr)/2;
x=Query(mij);
if(x>=val)
{
rez=mij;
dr=mij-1;
}
else
st=mij+1;
}
return rez;
}
int main()
{
int i,next,now,total,inc;
ifstream fin("order.in");
fin>>n;
fin.close();
for(i=1;i<=n;i++)
Update(i,1);
ofstream fout("order.out");
now=1;
for(i=1;i<=n;i++)
{
next=now;
total=Query(n);
inc=Query(now);
if(total-inc>=i)
next=inc+i;
else
{
next=i-(total-inc);
next=next%total;
if(next==0)
next=total;
}
now=CautareBinara(next);
fout<<now<<' ';
Update(now,-1);
}
fout<<"\n";
fout.close();
return 0;
}