Cod sursa(job #69283)

Utilizator vlad_popaVlad Popa vlad_popa Data 2 iulie 2007 15:14:12
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <cstdio>

#define FIN "order.in"
#define FOUT "order.out"
#define NMAX 1<<16

int A[NMAX], N, elim;

void read ()
{
    scanf ("%d\n", &N);
}

#define ns (nod << 1)
#define nd (ns + 1)
#define mj ((st + dr) >> 1)

int count (int nod, int st, int dr, int a, int b)
{
    if (a <= st && dr <= b)
        return A[nod];
    else
    {
        int val = 0;
        
        if (a <= mj)
            val = count (ns, st, mj, a, b);
        if (b > mj)
            val += count (nd, mj + 1, dr, a, b);

        return val;
    }
}

void update (int nod, int st, int dr, int p)
{
    if (st == dr)
        A[nod] = 1;
    else
    {
        if (p <= mj)
            update (ns, st, mj, p);
        else
            update (nd, mj + 1, dr, p);

        A[nod] = A[ns] + A[nd];
    }
}

void query (int nod, int st, int dr, int nr)
{
    if (!A[nod])
        elim = st + nr - 1;
    else
    {
        if (mj - st + 1 - A[ns] >= nr)
            query (ns, st, mj, nr);
        else
            query (nd, mj + 1, dr, nr - mj + st - 1 + A[ns]);
    }
}

void solve ()
{
    int poz, cntst, cnt, cntdr, nr;

    printf ("2 ");
    update (1, 1, N, 2);
    poz = 3;
    
    for (int pas = 2; pas <= N; ++ pas)
    {
        cntdr = N - poz - count (1, 1, N, poz, N) + 1;
        cnt = N - A[1];
        cntst = cnt - cntdr;

        if (pas <= cntdr)
        {
            query (1, 1, N, cntst + pas);
            printf ("%d ", elim);
            update (1, 1, N, elim);
            poz = elim + 1;
        }
        else
        {
            nr = (pas - cntdr) % cnt;
            if (nr == 0)
                nr = cnt;
            query (1, 1, N, nr);
            printf ("%d ", elim);
            update (1, 1, N, elim);
            poz = elim + 1;
        }
    }
}

int
 main ()
{
    freopen (FIN, "rt", stdin);
    freopen (FOUT, "wt", stdout);

    read ();
    solve ();

    return 0;
}