Cod sursa(job #1072156)

Utilizator gbi250Gabriela Moldovan gbi250 Data 4 ianuarie 2014 01:25:04
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#define SIZE 30000
using namespace std;

int n, value, index, next, needed_val, int_tree[ 4 * SIZE ];

inline void update(int, int, int);
inline int query(int, int, int);

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

    value = 1;

    for(int i=1; i<=n; ++i)
    {
        index = i;
        update(1, 1, n);
    }
    value = 0;
    next = 2;

    for(int i = 0; i < n; ++i)
    {
        next = ( next + i ) % int_tree[1];

        if( !next )
        {
            needed_val = int_tree[1];
            next = 1;
        }
        else
            needed_val = next;

        index = query(1, 1, n);

        printf("%d ", index);

        update(1, 1, n);
    }
    return 0;
}

inline void update(int node, int left, int right)
{
    if( left == right)
    {
        int_tree[ node ] = value;
        return ;
    }

    int middle = ( left + right ) / 2;

    if( index <= middle )
        update( 2 * node, left, middle );
    else
        update( 2 * node + 1, middle + 1, right );

    int_tree[ node ] = int_tree[ 2 * node ] + int_tree[ 2 * node + 1 ];
}

inline int query(int node, int left, int right)
{
    if( left == right )
        return left;

    int middle = ( left + right ) / 2;

    if( needed_val <= int_tree[ 2 * node ] )
        return query( 2 * node, left, middle);
    else
    {
        needed_val -= int_tree[ 2 * node ];
        return query( 2 * node + 1, middle + 1, right);
    }
}