Pagini recente » Cod sursa (job #90244) | Cod sursa (job #3339077) | Cod sursa (job #746744) | Cod sursa (job #3348696) | Cod sursa (job #3320274)
#include <stdio.h>
const int MAX_N = 30'000;
struct Aib {
int n;
int aib[2 * MAX_N + 1];
void init(int _n) {
n = _n;
}
void set(int pos) {
for(; pos <= n; pos += pos & -pos) {
aib[pos]++;
}
}
int query(int pos) {
int ret = 0;
for(; pos > 0; pos &= pos - 1) {
ret += aib[pos];
}
return ret;
}
int find_idx(int start, int k) {
int pref_sum = query(start);
int idx = 0;
int sum = 0;
for(int step = (1 << 17); step > 0; step /= 2) {
if(idx + step <= start) {
sum += aib[idx + step];
idx += step;
continue;
}
if(idx + step > n) {
continue;
}
int x = idx + step - start - (sum + aib[idx + step] - pref_sum);
if(idx + step <= n && x < k) {
sum += aib[idx + step];
idx += step;
}
}
return idx + 1;
}
};
Aib aib;
int main() {
FILE* fin = fopen("order.in", "r");
FILE* fout = fopen("order.out", "w");
int n;
fscanf(fin, "%d", &n);
aib.init(2 * n);
int last = 0;
for(int i = 0; i < n; i++) {
int kth = i % (n - i) + 1;
int idx = (aib.find_idx(last + 1, kth) - 1) % n;
aib.set(idx + 1);
aib.set(idx + 1 + n);
fprintf(fout, "%d ", idx + 1);
last = idx;
}
fprintf(fout, "\n");
fclose(fin);
fclose(fout);
return 0;
}