Cod sursa(job #1470802)

Utilizator borcanirobertBorcani Robert borcanirobert Data 12 august 2015 12:50:19
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
using namespace std;

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

const int MAX = 30010;
int a[MAX], N;
int AIB[MAX];
int p[MAX];

void Update( int poz, int nr );
int Sum( int x );
int BinarySearch( int nr );
int NZero( int x )
{
    return ( x xor ( x - 1 ) ) & x;
}

int main()
{
    int i, pos;

    fin >> N;
    for ( i = 1; i <= N; i++ )
    {
        fin >> a[i];
        Update( i, 1 );
    }

    for ( i = N; i >= 1; i-- )
    {
        pos = BinarySearch(a[i]);
        p[pos] = i;
        Update( pos, -1 );
    }

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

    fin.close();
    fout.close();
    return 0;
}

void Update( int poz, int nr )
{
    int i;

    for ( i = poz; i <= N; i += NZero(i) )
        AIB[i] += nr;
}

int Sum( int x )
{
    int i, s = 0;

    for ( i = x; i > 0; i -= NZero(i) )
        s += AIB[i];

    return s;
}

int BinarySearch( int nr )
{
    int st = 1, dr = N, mid;
    int s;
    int ret;

    while ( st <= dr )
    {
        mid = ( st + dr ) / 2;
        s = Sum(mid);
        if ( s < nr )
            st = mid + 1;
        else
            if ( s > nr )
                dr = mid - 1;
            else
                ret = mid, dr = mid - 1;
    }
    return ret;
}