Cod sursa(job #827739)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 2 decembrie 2012 16:21:59
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <cstdlib>

#define left_son ((nod) << 1)
#define right_son ((nod) << 1) +1
#define MAX_SIZE 1 << 16

int N,tree[MAX_SIZE] , poz;

void update_tree(int nod, int left, int right, int val,int pozition)
{
    if(left == right)
    {
        tree[nod] = val;
        return;
    }

    int middle = (left+right) / 2;

    if(pozition <= middle) update_tree(left_son, left, middle,val,pozition);
    else update_tree(right_son, middle+1, right,val,pozition);

    tree[nod] = tree[left_son] + tree[right_son];
}

void query_tree(int nod, int left, int right, int value)
{

    if(left == right)
    {
        poz = left;
        return;
    }

    int middle = (left+right) / 2;

    if(tree[left_son] >= value) query_tree(left_son, left, middle, value);
    else query_tree(right_son, middle+1, right, value-tree[left_son]);
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&N);

    for(int i=1; i<=N; i++)
    {
        poz = i;
        update_tree(1, 1, N , 1, i);
    }
    int next_kid = 1;
    for(int i=1; i<=N; i++)
    {
        next_kid = (next_kid + i + tree[1]) % tree[1];
        if(next_kid == 0) next_kid = tree[1];

        query_tree(1, 1, N, next_kid);
        update_tree(1, 1, N,0,poz);

        printf("%d ",poz);
        next_kid--;
    }

    return 0;
}