Cod sursa(job #1669294)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 30 martie 2016 17:02:28
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
#define MAXN 30005
FILE *f=fopen("order.in","r"), *g=fopen("order.out","w");

int N, ai[3*MAXN];

void Pune( int nr, int k1, int k2, int poz ){

    ai[poz] ++;

    if( k1 == k2 ) return;

    int mij = (k1+k2)/2;

    if( nr <= mij )
        Pune( nr, k1, mij, poz*2 );
    else
        Pune( nr, mij+1, k2, poz*2+1 );
}

void Creare_ai(){

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

}

int Cate( int k3, int k4, int k1, int k2, int poz ){

    if( k3 <= k1 && k2 <= k4 )
        return ai[poz];

    int mij = (k1+k2)/2, sum = 0;

    if( k3 <= mij )
        sum += Cate( k3, k4, k1, mij, poz*2 );

    if( k4 >= mij+1 )
        sum += Cate( k3, k4, mij+1, k2, poz*2+1 );

    return sum;

}

int Sari( int sar, int k1, int k2, int poz ){
int mij = (k1+k2)/2;

    ai[poz] --;  // Din intervalul asta o sa se elimine un element

    if( k1 == k2 )
        return k1;

    if( sar <= ai[poz*2] )
        return Sari( sar, k1,mij,poz*2 );

    else
        return Sari( sar - ai[poz*2], mij+1,k2,poz*2+1 );

}

void Rezolvare(){
int pas, poz, sar;

    poz = 1;    // Ultima pozitie eliminata

    for( pas=1; pas<=N; pas++ ){

        sar = pas + Cate( 1,poz, 1,N,1 );

        sar %= ai[1];
        if( sar == 0 )
            sar = ai[1];

        poz = Sari( sar, 1,N,1 );

        fprintf(g,"%d ",poz);

    }

}

int main(){

    fscanf(f,"%d\n",&N);
    Creare_ai();
    Rezolvare();

return 0;
}