Cod sursa(job #1425559)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 27 aprilie 2015 17:37:57
Problema Order Scor 100
Compilator cpp Status done
Runda pregatire-lot-aib Marime 1.22 kb
#include<fstream>

using namespace std;

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

const int nmax = 30000;
int n;
int aib[ nmax + 1 ];

inline int lsb( int x ) {
    return (x & -x);
}
void update( int pos, int shp ) {
    for( int i = pos; i <= n; i += lsb( i ) ) {
        aib[ i ] += shp;
    }
}
int query( int pos ) {
    int ans = 0;
    for( int i = pos; i > 0; i -= lsb( i ) ) {
        ans += aib[ i ];
    }
    return ans;
}
int main() {
    int x, n2, ok;
    fin >> n;
    for( int i = 1; i <= n; ++ i ) update( i, 1 );

    for( n2 = 1; (n2 << 1) <= n; n2 <<= 1 ) {
    }
    x = 1;
    for( int i = 1; i <= n; ++ i ) {
        int cate = i % (n + 1 - i);
        if ( cate == 0 ) cate = n + 1 - i;

        int aux = query( n ) - query( x );
        if ( cate > aux ) {
            ok = 0; cate -= aux;
        } else {
            ok = query( x );
        }

        int sol = 0;
        for( int step = n2; step > 0; step >>= 1 ) {
            if ( sol + step < n && query( sol + step ) < ok + cate ) {
                sol += step;
            }
        }

        update( sol + 1, -1 );
        fout << sol + 1 << " ";
        x = sol + 1;
    }
    fout << "\n";
    fin.close();
    fout.close();
    return 0;
}