Cod sursa(job #1423874)

Utilizator Athena99Anghel Anca Athena99 Data 22 aprilie 2015 21:48:59
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>

using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");

const int nmax= 30000;
const int pmax= 15;

int n;
int ft[nmax+1];

void ft_update( int p, int x ) {
    for ( int i= p; i<=n; i= 2*i-(i&(i-1)) ) {
        ft[i]+= x;
    }
}

int ft_query( int p ) {
    int sol= 0;
    for ( int i= p; i>0; i&= i-1 ) {
        sol+= ft[i];
    }
    return sol;
}

int main(  ) {
    fin>>n;
    for ( int i= 1; i<=n; ++i ) {
        ft_update(i, 1);
    }

    for ( int i= 1, aux= n, pos= 2; i<=n; ++i ) {
        int sol= 0;
        for ( int step= 1<<pmax; step>0; step/= 2 ) {
            if ( sol+step<=n && ft_query(sol+step)<pos ) {
                sol+= step;
            }
        }

        fout<<sol+1<<" ";
        ft_update(sol+1, -1);

        pos+= i, --aux;
        if ( aux>0 ) {
            pos= pos%aux;
            if ( pos==0 ) {
                pos= aux;
            }
        }
    }
    fout<<"\n";

    return 0;
}