Cod sursa(job #603653)

Utilizator SpiderManSimoiu Robert SpiderMan Data 18 iulie 2011 11:19:32
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
# include <cstdio>

const char *FIN = "order.in", *FOU = "order.out";
const int MAX = 30005;

int N, aib[MAX];

void update (int nod, int x) {
    for (++nod; nod < MAX; nod += nod & -nod)
        aib[nod] += x;
}

int query (int nod) {
    int sol = 0;
    for (++nod; nod; nod -= nod & -nod)
        sol += aib[nod];
    return sol;
}

int bs (int x) {
    int i, cnt;
    for (cnt = 1; cnt <= N; cnt <<= 1);
    for (i = -1; cnt; cnt >>= 1)
        if (i + cnt < N && query (i + cnt) < x)
            i += cnt;
    return ++i;
}

int main (void) {
    fscanf (fopen (FIN, "r"), "%d", &N);
    for (int i = 0; i < N; ++i)
        update (i, 1);
    freopen (FOU, "w", stdout);
    for (int sol = 1, i = 0; i < N; ++i) {
        sol += i, sol %= N - i;
        int p = bs (sol + 1);
        if (i) printf (" ");
        printf ("%d", p + 1);
        update (p, -1);
    }
}