Cod sursa(job #1814086)

Utilizator catu_bogdan_99Catu Bogdan catu_bogdan_99 Data 23 noiembrie 2016 17:21:30
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
using namespace std;

#define NMAX 30005

int n;

struct aib {

    int v[ NMAX ];

    void add ( int poz, int k ) {
        for ( int i = poz; i <= n; i += ( i & ( -i ) )  )
            v[ i ] += k;
    }

    int suma ( int k ) {
        int i, pas;
        i = 0;
        pas = 1 << 17;

        while ( pas ) {
            if ( i + pas <= n && v[ i + pas ] < k ) {
                i += pas;
                k -= v[ i ];
            }
            pas /= 2;
        }
        return i + 1;
    }

} arbore;

int main () {

    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);

    int i, j, k, r;

    scanf("%d",&n);

    for ( i = 1; i <= n; ++i )
        arbore.add( i, 1 );

    k = 2;
    for ( i = 2; i <= n; ++i ) {
        r = arbore.suma( k );
        arbore.add( r, -1 );
        printf("%d ",r);
        k = ( k + i - 1 ) % ( n - i + 1 );
        if ( k == 0 ) k = n - i + 1;
    }

    printf("%d ",arbore.suma( k ));

    return 0;

}