Cod sursa(job #827449)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 2 decembrie 2012 01:53:55
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<cstdio>

#define Nmax 65536

int N, poz, val, aint[Nmax];

void update(int nod, int st, int dr) {

    if(st == dr) {
        aint[nod] = val;
        return;
    }

    int mij = (st+dr)/2;
    if(poz <= mij)
        update(nod*2, st, mij);
    else
        update(nod*2+1, mij+1, dr);

    aint[nod] = aint[nod*2] + aint[nod*2+1];
}

void query(int nod, int st, int dr, int sum) {

    if(st == dr) {
        poz = st;
        return;
    }

    int mij = (st+dr)/2;
    if(aint[nod*2] >= sum)
        query(nod*2, st, mij, sum);
    else
        query(nod*2+1, mij+1, dr, sum-aint[nod*2]);
}

void read_data() {

    freopen("order.in","r",stdin);
    int i;

    scanf("%d",&N);
    val = 1;
    for(i=1; i<=N; ++i) {
        poz = i;
        update(1, 1, N);
    }
}

void solve() {

    freopen("order.out","w",stdout);
    int i, next;

    val = 0;
    next = 1;
    for(i=1; i<=N; ++i) {
        next = (next + i + aint[1]) % aint[1];
        if(next == 0)
            next = aint[1];
        query(1, 1, N, next);
        update(1, 1, N);
        printf("%d ",poz);
        --next;
    }
}

int main() {

    read_data();
    solve();

    return 0;
}