Cod sursa(job #955426)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 31 mai 2013 19:25:06
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<stdio.h>

int Arbi[40001] , poz , n , nr , ok;

void update(int nod , int st , int dr)
{
    if(st == dr)
    {
        Arbi[nod] = ok;
        return ;
    }
    int med = (st + dr) >> 1;
    if(poz <= med)
        update(2 * nod , st , med);
    if(poz > med)
        update(2 * nod + 1 , med + 1 , dr);
    Arbi[nod] = Arbi[2 * nod] + Arbi[2 * nod + 1];
}

void query(int nod , int st , int dr , int nr)
{
    if(st == dr)
    {
        poz = st;
        return ;
    }
    int med = (st + dr) >> 1;
    if(nr <= Arbi[2 * nod])
        query(2 * nod , st , med , nr);
    if(nr > Arbi[2 * nod])
        query(2 * nod + 1 , med + 1 , dr , nr - Arbi[2 * nod]);
}

int main()
{
    freopen("order.in" , "r" , stdin);
    freopen("order.out" , "w" , stdout);
    scanf("%d" , &n);
    ok = 1;
    for(int i = 1 ; i <= n ; ++ i)
        poz = i , update(1 , 1 , n);
    ok = 0;
    nr = 1;
    for(int i = 1 ; i <= n ; ++ i)
    {
        nr = (nr + i) % Arbi[1];
        if(nr == 0)
            nr = Arbi[1];
        query(1 , 1 , n , nr);
        printf("%d " , poz);
        -- nr;
        ok = 0;
        update(1 , 1 , n);
    }
    return 0;
}