Pagini recente » Cod sursa (job #736139) | Cod sursa (job #1481623) | Cod sursa (job #2072146) | Cod sursa (job #741315) | Cod sursa (job #1757857)
#include <fstream>
#define VAL 30005
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int N, i, p, x, be, a;
int aib[VAL], dif, K;
int zero(int x)
{
return x&(-x);
}
void update(int i)
{
while (i<=N)
{
aib[i]++;
i+=zero(i);
}
}
void scade(int i)
{
while (i<=N)
{
aib[i]--;
i+=zero(i);
}
}
int verif(int a, int p)
{
int x=0;
int y=0;
while (p!=0)
{
x+=aib[p];
p-=zero(p);
}
while (a!=0)
{
y+=aib[a];
a-=zero(a);
}
return y-x;
}
int cautbin(int be, int en, int dif)
{
int mid, ans;
while (be<=en)
{
mid=(be+en) / 2;
if (verif(mid, K-1)>=dif)
{
if (verif(mid, K-1)==dif)
ans=mid;
en=mid-1;
}
else
be=mid+1;
}
return ans;
}
int main()
{
fin >> N;
for (i=1; i<=N; i++)
update(i);
p=1;
for (i=1; i<=N; i++)
{
p++;
if (p>N)
p=1;
x=verif(N, p-1);
if (x<i)
{
be=1;
dif=i-x;
}
else
{
be=p;
dif=i;
}
if (dif>N-i+1)
{
a=dif / (N-i+1);
dif-=a*(N-i+1);
if (dif==0)
dif=N-i+1;
}
K=be;
p=cautbin(be, N, dif);
scade(p);
fout << p << " ";
}
fin.close();
fout.close();
return 0;
}