Cod sursa(job #227569)

Utilizator Mishu91Andrei Misarca Mishu91 Data 4 decembrie 2008 21:33:27
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>

#define MAX_N 30005
#define left (nod << 1)
#define right ((nod << 1) + 1)
#define mij ((li + lf) >> 1)

int N, A[MAX_N*4];
int poz, val, x;

void update(int nod, int li, int lf)
{
    if(li == lf)
    {
        A[nod] = val;
        return;
    }
    if(mij >= poz) update(left, li, mij);
    else           update(right, mij+1, lf);
    A[nod] = A[left] + A[right];
}

void find(int nod, int li, int lf)
{
    if(lf < poz)
    {
        x += A[nod];
        return;
    }
    if(li == lf) return;
    find(left, li, mij);
    if(poz > mij) find(right, mij+1, lf);
}

void query(int nod, int li, int lf, int x)
{
    if(A[nod] == x && li == lf)
    {
        A[nod] = 0;
        poz = li;
        printf("%d ", poz);
        return;
    }
    if(A[left] >= x) query(left, li, mij, x);
    else query(right, mij+1, lf, x - A[left]);
    A[nod] = A[left] + A[right];
}

int main()
{
    freopen("order.in","rt",stdin);
    freopen("order.out","wt",stdout);

    scanf("%d",&N);

    for(int i = 1; i <= N; ++i)
    {
        if(i == 2) val = 0;
        else val = 1;
        poz = i;
        update(1, 1, N);
    }

    printf("2 ");
    poz = 2;

    for(int i = 2; i <= N; ++i)
    {
        x = 0;
        find (1, 1, N);
        x +=i;
        int k = (N - i + 1);
        x %= k;
        if(!x) x = k;
        query(1, 1, N, x);
    }
}