Pagini recente » Cod sursa (job #243570) | Cod sursa (job #2418580) | Profil Diana69 | Cod sursa (job #1021949) | Cod sursa (job #918881)
Cod sursa(job #918881)
#include <iostream>
#include <fstream>
#include <cstdio>
using namespace std;
int n, aib[30010];
inline void Update(int poz, int val)
{
while (poz <= n)
{
aib[poz] += val;
poz = poz + (poz & -poz);
}
}
inline int Query(int poz)
{
int rez = 0;
while (poz)
{
rez = rez + aib[poz];
poz = poz - (poz & -poz);
}
return rez;
}
inline int CautareBinara(int val)
{
int rez, st, dr, mij, x;
st = 1;
dr = n;
while (st <= dr)
{
mij = (st+dr)>>1;
x = Query(mij);
if (x >= val)
{
rez = mij;
dr = mij - 1;
}
else
st = mij + 1;
}
return rez;
}
inline void Read()
{
ifstream f ("order.in");
f>>n;
f.close();
}
inline void Solve()
{
ofstream g ("order.out");
int i;
for (i=1; i<=n; i++)
Update(i, 1);
int now, next, inc, total;
now = 1;
for (i=1; i<=n; i++)
{
inc = Query(now);
total = Query(n);
if (total - inc >= i)
{
next = inc + i;
}
else
{
next = i - (total - inc);
next = next%total;
if (next == 0)
next = total;
}
now = CautareBinara(next);
g<<now<<" ";
Update(now, -1);
}
g.close();
}
int main()
{
Read();
Solve();
return 0;
}