Cod sursa(job #1809921)

Utilizator giotoPopescu Ioan gioto Data 19 noiembrie 2016 13:40:46
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
using namespace std;

int Sol, n, Arb[120044];
inline void Build(int nod, int st, int dr){
    if(st == dr)
        {Arb[nod] = 1; return ;}
    int mij = (st + dr) / 2;
    if(mij >= st) Build(nod * 2, st , mij);
    if(mij < dr) Build(nod * 2 + 1, mij + 1, dr);
    Arb[nod] = Arb[nod * 2] + Arb[nod * 2 + 1];
}
inline void Query(int st, int dr, int nod, int pos){
    if(st == dr){
        Sol = st;
        return ;
    }
    int mij = (st + dr) / 2;
    if(Arb[nod * 2] >= pos) Query(st, mij, nod * 2, pos);
    else Query(mij + 1, dr, nod * 2 + 1, pos - Arb[nod * 2]);
}
inline void Update(int st, int dr, int nod, int pos){
    if(st == dr){
        Arb[nod] = 0;
        return ;
    }
    int mij = (st + dr) / 2;
    if(pos <= mij) Update(st, mij , nod * 2, pos);
            else   Update(mij + 1, dr, nod * 2 + 1, pos);
    Arb[nod] = Arb[nod * 2] + Arb[nod * 2 + 1];
}
int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    scanf("%d", &n);
    Build(1, 1, n);
    bool ok = 0;
    int m = n, z = 1;
    for(int i = 1; i <= n ; ++i){
        z = z + i - ok;
        z %= m;
        Sol = 0;
        if(!z) z = m;
        Query(1, n, 1, z);
        printf("%d ", Sol);
        Update(1, n, 1, Sol);
        ok = 1; --m;
    }
    return 0;
}