Cod sursa(job #1794626)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 1 noiembrie 2016 15:54:58
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
# include <fstream>
# include <iostream>
# include <deque>
# include <assert.h>

using namespace std;

# include <stdio.h>
# include <stdlib.h>

# define MAX_N 100000

class aib {
    int n;
    int * s;

    public:
    aib( int _n ) {
        n = _n;
        s = new int[1 + n];

        for ( int i = 0; i <= n; i ++ )
            s[i] = ( i & -i );
    }

    void update( int pos, int val ) {
        while ( pos <= n ) {
            s[pos] += val;
            pos += ( pos & -pos );
        }
    }

    int operator[]( int pos ) {
        int S;

        S = 0;
        while ( pos > 0 ) {
            S += s[pos];
            pos -= ( pos & -pos );
        }

        return S;
    }

    int cbin( int val ) {
        int b=1, e=n, m, p, l=1000000;

        while( b<=e )
        {
            m=(b+e)/2;
            p=(*this)[m];

            if( p==val && l>m )
                l=m;
            else
                if( p<val )
                    b=m+1;
                else
                    e=m-1;
        }

        return l;
    }
};

# define MAX_N 30000

int v[1 + MAX_N];
int c[1 + MAX_N];

int main() {
    ifstream fin( "schi.in" );
    ofstream fout( "schi.out" );

    int n, i, nr, p;

    fin >> n;
    aib s( n );

    for ( i = 1; i <= n; i ++ )
        fin >> v[i];

    for ( i = n; i > 0; i -- ) {
        p = s.cbin( v[i] );
        c[p] = i;
        s.update( p, -1 );
    }

    for ( i = 1; i <= n; i ++ )
        fout << c[i] << '\n';

    fin.close();
    fout.close();

    return 0;
}