Pagini recente » Cod sursa (job #2344285) | Cod sursa (job #1037104) | Cod sursa (job #1826049) | Cod sursa (job #2648385) | Cod sursa (job #2920314)
#include <stdio.h>
#define MAX_N 30005
int aib[MAX_N];
int res[MAX_N];
static inline long long int query(int pos) {
long long int ans = 0;
while (pos) {
ans += aib[pos];
pos -= pos & (-pos);
}
return ans;
}
static inline void update(int pos, int val, const int &nrn) {
while (pos <= nrn) {
aib[pos] += val;
pos += pos & (-pos);
}
}
static inline long long int interval(int pos1, int pos2) {
return query(pos2) - query(pos1 - 1);
}
int main () {
FILE *fin, *fout;
int n, i, step;
int st, dr, mij;
int stepCalc, p, q;
int pos, last;
fin = fopen("order.in", "r");
fscanf(fin, "%d", &n);
for (i = 1; i <= n; i++)
update(i, 1, n);
fclose(fin);
step = 1; last = 2;
for (i = 1; i <= n; i++) {
st = last; dr = n;
while (dr - st > 1) {
mij = (st + dr) / 2;
if (interval(last, mij) < step)
st = mij;
else
dr = mij;
}
p = interval(last, n);
if (p < step) {
stepCalc = step - p;
while (stepCalc > 0) {
st = 0, dr = n;
while (dr - st > 1) {
mij = (st + dr) / 2;
if (interval(1, mij) < stepCalc)
st = mij;
else
dr = mij;
}
q = stepCalc - interval(1, st);
if (q > 0)
stepCalc -= interval(1, n);
else
stepCalc = q;
}
}
if (interval(last, st) < step)
st++;
pos = st;
last = pos;
res[i] = pos;
update(pos, -1, n);
step++;
}
fout = fopen("order.out", "w");
for (i = 1; i <= n; i++)
fprintf(fout, "%d ", res[i]);
fclose(fout);
return 0;
}