Pagini recente » Cod sursa (job #2744773) | Cod sursa (job #1325959) | Cod sursa (job #2447162) | Cod sursa (job #2837823) | Cod sursa (job #1464521)
#include <fstream>
using namespace std;
#define Nmax 30001
int n, logN;
int AIB[Nmax];
void update(int, int) ;
int sum(int) ;
int search(int) ;
int main()
{
freopen("order.in", "r", stdin);
freopen("order.out", "w", stdout);
int i, nr, k, poz;
scanf("%d", &n);
for(i = 1; i <= n; ++i) update(i, 1);
for(logN = 0; (1 << logN) < n; ++logN) ;
for(poz = i = 1; i <= n; ++i)
{
nr = i % (n + 1 - i);
if(nr == 0) nr = n + 1 - i;
k = n + 1 - i - sum(poz);
if(nr <= k) poz = search(n + 1 - i - k + nr);
else poz = search(nr - k);
update(poz, -1);
printf("%d ", poz);
fflush(stdout);
}
return 0;
}
void update(int poz, int val)
{
for(; poz <= n; poz += poz & (-poz)) AIB[poz] += val;
}
int sum(int poz)
{
int s;
for(s = 0; poz > 0; poz &= poz - 1) s += AIB[poz];
return s;
}
int search(int val)
{
int poz, step, rez;
for(poz = 0, step = (1 << logN), rez = 0; step > 0; step >>= 1)
if(poz + step <= n)
{
if(AIB[poz + step] < val)
{
poz += step;
val -= AIB[poz];
}
else if(AIB[poz + step] == val) rez = poz + step;
}
if(val == 0) rez = poz;
return rez;
}