Pagini recente » Cod sursa (job #3138233) | Cod sursa (job #521149) | Cod sursa (job #1418759) | Cod sursa (job #2709113) | Cod sursa (job #2954412)
#include <iostream>
using namespace std;
int N;
int BIT[30005];
FILE *in = fopen("order.in", "r"), *out = fopen("order.out", "w");
void update(int pos, int val){
for (int i = pos; i <= N; i += i & (-i))
BIT[i] += val;
}
int query(int pos){
int sum = 0;
for (int i = pos; i >= 1; i -= i & (-i))
sum += BIT[i];
return sum;
}
int BS(int val){
int k, L = 1, R = N, M, S;
while (L <= R) {
M = (L + R) / 2;
S = query(M);
if (S < val)
L = M + 1;
else if (S > val)
R = M - 1;
else {
k = M;
while(query(k-1) == val && k > 0)
--k;
break;
}
}
return k;
}
int main()
{
fscanf(in, "%d", &N);
// Initialize BIT (BIT[i] = nr of not eliminated children in appropriate interval)
for (int i = 1; i <= N; ++i)
update(i, 1);
int L = N, steps, pos = 1, preL;
for (int i = 1; i <= N; ++i){
if (L > 1)
steps = i % L;
else
steps = 1;
preL = query(pos);
//
if (preL + steps > L) {
pos = BS(1);
steps -= L - preL + 1;
preL = query(pos);
}
//
pos = BS(preL + steps);
fprintf(out, "%d ", pos);
update(pos, -1);
L -= 1;
}
return 0;
}