Pagini recente » Cod sursa (job #2634520) | Cod sursa (job #1590101) | Cod sursa (job #3289166) | Cod sursa (job #438140) | Cod sursa (job #2440771)
#include <fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int nr,n,nrcp,aib[30005],poz,v[30005],nrx;
int ub(int x)
{
return (x&(-x));
}
void Add(int x, int val)
{
for(int i=x; i<=n; i+=ub(i))
aib[i]+=val;
}
int sum(int x)
{
int s=0;
for(int i=x; i>=1; i-=ub(i))
s+=aib[i];
return s;
}
int caz2(int nr, int n, int poz)
{
int st=1;
int dr=poz;
int mij=0;
int p=0;
int val=0;
while(st<=dr)
{
mij=(st+dr)/2;
val=sum(mij);
if(nr>val)
st=mij+1;
else
{
dr=mij-1;
if(v[mij]==0)
p=mij;
}
}
st=1;
dr=poz;
while(st<=dr)
{
mij=(st+dr)/2;
val=sum(mij);
if(nr<val)
dr=mij-1;
else
{
st=mij+1;
if(v[mij]==0)
p=mij;
}
}
return p;
}
int caz1(int nr, int n, int poz)
{
int st=poz, dr=n, mij=0, p=0, val=0;
while(st<=dr)
{
mij=(st+dr)/2;
val=sum(mij);
if(nr>val)
st=mij+1;
else
{
dr=mij-1;
if(v[mij]==0)
p=mij;
}
}
st=poz, dr=n, mij=0, p=0, val=0;
while(st<=dr)
{
mij=(st+dr)/2;
val=sum(mij);
if(nr<val)
dr=mij-1;
else
{
st=mij+1;
if(v[mij]==0)
p=mij;
}
}
return p;
}
int main()
{
f>>n;
for(int i=1; i<=n; i++)
Add(i,1);
poz=2;
Add(2,-1);
v[2]=1;
nrx=2;
g<<2<<' ';
nrcp=n-1;
while(nrcp!=0)
{
nr=(nrx-1)%nrcp+1;
if(sum(n)-sum(poz)<nr)
poz=caz2(nr-(sum(n)-sum(poz)),n,poz);
else
poz=caz1(nr+sum(poz),n,poz);
Add(poz,-1);
v[poz]=1;
nrcp--;
nrx++;
g<<poz<<' ';
}
return 0;
}