Cod sursa(job #995148)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 7 septembrie 2013 18:53:36
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <iostream>
using namespace std;

const int NMAX = 30003;

int AIB[NMAX], N, st;

inline void AIB_build () {

    int i, j;
    for (i = 1; i <= N; ++i)
        for (j = i; j <= N; j += j & -j)
            ++AIB[j];

}

inline int AIB_search (int s) {

    int i = st, r = 0, best;
    for (; i; i >>= 1)
        if (r + i <= N)
            if (!(s - AIB[i + r]))
                best = i + r;
            else
                if (s > AIB[i + r])
                    r += i,
                    s -= AIB[r];
    return best;

}

inline void AIB_update (int i) {

    for (; i <= N; i += i & -i)
        --AIB[i];

}

int main () {

    freopen ("order.in", "r", stdin);
    freopen ("order.out", "w", stdout);
    int w = 1, m, i, k;
    cin >> N;
    for (st = 1; st < N; st <<= 1);
    m = N;
    AIB_build ();
    for (i = 1; i <= N; ++i) {
        w = (w + i) % m;
        if (!w)
            w = m;
        k = AIB_search (w);
        cout << k << ' ';
        AIB_update (k);
        --m;
        --w;
    }

}