Pagini recente » Cod sursa (job #308042) | Cod sursa (job #1202767) | Cod sursa (job #2937839) | Cod sursa (job #1471798) | Cod sursa (job #2920312)
#include <stdio.h>
#define MAX_N 30005
int aib[MAX_N];
int res[MAX_N];
inline long long int query(int pos) {
long long int ans = 0;
while (pos) {
ans += aib[pos];
pos -= pos & (-pos);
}
return ans;
}
inline void update(int pos, int val, const int &nrn) {
while (pos <= nrn) {
aib[pos] += val;
pos += pos & (-pos);
}
}
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 pos, last, cont;
int stepCalc;
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++) {
cont = 0; st = last; dr = n;
while (dr - st > 1) {
mij = (st + dr) / 2;
if (interval(last, mij) < step)
st = mij;
else
dr = mij;
}
if (interval(last, n) < step) {
cont = interval(last, n);
stepCalc = step - cont;
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;
}
if (stepCalc - interval(1, st) > 0)
stepCalc -= interval(1, n);
else
stepCalc -= interval(1, st);
}
}
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;
}