Cod sursa(job #44948)

Utilizator victorsbVictor Rusu victorsb Data 31 martie 2007 20:47:56
Problema Order Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <cstdio>

#define Nmax 30005
#define Amax 131072

int n, a, b, vl;
int sir[Nmax], ai[Amax];

void citire()
{
    int i;
    
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
        scanf("%d", &sir[i]);
}

void update(int nod, int st, int dr)
{
    if (st == dr)
        ai[nod] = vl;
    else
    {
        int mij = (st + dr) / 2;
        
        if (a <= mij)
            update(nod*2, st, mij);
        else
            update(nod*2+1, mij+1, dr);
        
        ai[nod] = ai[nod*2] + ai[nod*2+1];
    }
}

int query1(int nod, int st, int dr)
{
    if (a <= st && dr <= b)
        return ai[nod];
    else
    {
        int mij = (st + dr) / 2, ret = 0;
        
        if (a <= mij)
            ret += query1(nod*2, st, mij);
        
        if (mij < b)
            ret += query1(nod*2+1, mij+1, dr);
        
        return ret;
    }
}

int query2(int nod, int st, int dr, int pos)
{
    if (st == dr)
        return st;
    else
    {
        int mij = (st + dr) / 2;
        
        if (pos <= ai[nod*2])
            return query2(nod*2, st, mij, pos);
        else
            return query2(nod*2+1, mij+1, dr, pos - ai[nod*2]);
    }
}

void solve()
{
    int i, pos = 1, inc, nr, p;
    
    vl = 1;
    for (i = 1; i <= n; ++i)
    {
        a = i;
        update(1, 1, 2*n);
        a = i + n;
        update(1, 1, 2*n);
    }
    
    vl = 0;
    for (i = 1, nr = n; i <= n; ++i, --nr)
    {
        inc = i % nr;
        if (inc == 0)
            inc = nr;        
        
        a = 1;
        b = pos;
        inc += query1(1, 1, 2*n);
        
        p = query2(1, 1, 2*n, inc);
        if (p > n) p -= n;
        pos = p;
        printf("%d ", p);
        
        a = p;
        update(1, 1, 2*n);
        
        a = p + n;
        update(1, 1, 2*n);
    }
    printf("\n");
}

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