Cod sursa(job #1473539)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 19 august 2015 16:46:18
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <cstring>

#define NMAX 30007

using namespace std;
FILE *fin, *fout;
int arb[4*NMAX], n, next, ans, rem;

void build(int st, int dr, int nod)
{
    if(st == dr)
    {
        arb[nod] = 1;
        return ;
    }
    int mij = (st + dr)/2;
    build(st, mij, 2*nod);
    build(mij+1, dr, 2*nod+1);
    arb[nod] = arb[2*nod] + arb[2*nod+1];
}
void update(int st, int dr, int pos, int nod)
{
    if(st == dr)
    {
        arb[nod] = 0;
        return ;
    }
    int mij = (st+dr)/2;
    if(pos <= arb[2*nod]) update(st, mij, pos, 2*nod);
    else update(mij+1, dr, pos - arb[2*nod], 2*nod+1);
    arb[nod] = arb[2*nod] + arb[2*nod + 1];
}
int query(int st, int dr, int pos, int nod)
{
    if(st == dr) return st;
    int mij = (st + dr)/2;
    if(pos <= arb[2*nod]) return query(st, mij, pos, 2*nod);
    else return query(mij+1, dr, pos - arb[2*nod], 2*nod + 1);
}

void citire()
{
    scanf("%d", &n);
}
void init()
{
    next = 2;
    rem = n;
    build(1, n, 1);
}
void solve()
{
    for(int i = 1; i<= n; ++i)
    {
        next = (next + i - 1)%rem;
        if(!next) next = rem;
        ans = query(1, n, next, 1);
        printf("%d ", ans);
        update(1, n, next, 1);
        rem--;
    }
}

int main()
 {
    fin = freopen("order.in", "r", stdin);
    fout = freopen("order.out", "w", stdout);
    citire();
    init();
    solve();
    fclose(fin);
    fclose(fout);
    return 0;
 }