Cod sursa(job #1559047)

Utilizator BLz0rDospra Cristian BLz0r Data 29 decembrie 2015 22:54:11
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
using namespace std;

#define Nmax 30002
#define LSB(x) ( (x) & -(x) )

FILE *f = fopen ( "order.in", "r" );
FILE *g = fopen ( "order.out", "w" );

int N, AIB[Nmax];

void Update ( int poz, int val ){

    for ( int i = poz; i <= N; i += LSB(i) )
        AIB[i] += val;
}

int Query ( int poz ){

    int ret = 0;
    for ( int i = poz; i > 0; i -= LSB(i) )
        ret += AIB[i];

    return ret;
}


int BSearch ( int Pasi ){

    int st = 1, dr = N, poz, sol;

    while ( st <= dr ){
        poz = st + (( dr - st ) >> 1);

        int val = Query( poz );

        if ( val == Pasi )
            sol = poz;

        if ( val < Pasi )
            st = poz+1;
        else
            dr = poz-1;
    }

    return sol;
}

int main(){

    fscanf ( f, "%d", &N );

    for ( int i = 1; i <= N; ++i )
        Update ( i, 1 );

    int Remain = N, Poz = 1;

    for ( int i = 1; i <= N; ++i ){

        Poz = ( Poz + i ) % Remain;
        if ( !Poz )
            Poz = Remain;

        int val = BSearch(Poz);

        fprintf ( g, "%d ", val );
        Update( val, -1 );

        Poz--;
        Remain--;

    }

    return 0;
}