Cod sursa(job #2783372)

Utilizator AlexNicuNicu Alexandru AlexNicu Data 14 octombrie 2021 12:40:43
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>

using namespace std;

ifstream cin ( "schi.in" );
ofstream cout ( "schi.out" );

#define NMAX 30000
#define INF 1000000001

int aint[4 * NMAX + 1];

void update1( int poz, int val ) {
    aint[poz] = val;
    while ( poz > 1 ) {
        if (poz % 2 == 0 )
            aint[poz / 2] = aint[poz] + aint[poz + 1];
        else
            aint[poz / 2] = aint[poz - 1] + aint[poz];
        poz /= 2;
    }
}

int query(int ind, int csta, int cdra, int cstq, int cdrq ) {
    if ( cstq <= csta && cdra <= cdrq ) {
        return aint[ind];
    } else {
        int aux = 0;
        //comparam cu mijlocul
        if ( cstq <= (csta + cdra) / 2 ) {
            aux = query(ind * 2, csta, (csta + cdra) / 2, cstq, cdrq);
        }
        if ( cdrq > (csta + cdra) / 2 ) {
            aux = aux + query(ind * 2 + 1, (csta + cdra) / 2 + 1, cdra, cstq, cdrq );
        }
        return aux;
    }
}

int v[30001], ans[30001];

int main() {
    int n, i, poz, p, verif_poz, ramane_val;
    cin >> n;
    for ( i = 0; i < n; i++ ) {
        cin >> v[i];
    }
    p = 2;
    while ( p < n )
        p = p * 2;
    for ( i = 0; i < n; i++ ) {
        update1( p + i, 1 );
    }
    for ( i = n - 1; i >= 0; i-- ) {
        verif_poz = 2;
        ramane_val = v[i];
        while ( verif_poz < p ) {
            if ( aint[verif_poz] >= ramane_val ) {
                verif_poz = verif_poz * 2;
            }else {
                ramane_val -= aint[verif_poz];
                verif_poz++;
            }
        }
        if ( aint[verif_poz] >= ramane_val ) {
          ans[verif_poz - p + 1] = i + 1;
          update1(verif_poz, 0);
        }
        else {
          ans[verif_poz - p + 2] = i + 1;
          update1(verif_poz + 1, 0);
        }
    }
    for ( i = 1; i <= n; i++ ) {
      cout << ans[i] << "\n";
    }
    return 0;
}