Cod sursa(job #3258834)

Utilizator andreidumitrache1709Dumitrache Andrei Bogdan andreidumitrache1709 Data 23 noiembrie 2024 20:01:03
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <bits/stdc++.h>
#define MAXN 30000
using namespace std;
int n , v[MAXN + 1] , ans[MAXN + 1] , aib[MAXN + 1];
void update( int pos ) {
    do {
        aib[pos]++;
        pos += pos & -pos;
    } while( pos <= n );
}
int query( int pos ) {
    int ans;
    ans = 0;
    while( pos ) {
        ans += aib[pos];
        pos &= pos - 1;
    }
    return ans;
}
int main() {
    ifstream cin( "schi.in" );
    ofstream cout( "schi.out" );
    int st , dr , mij , i;
    cin >> n;
    for( i = 1 ; i <= n ; i++ )
        cin >> v[i];
    for( i = n ; i >= 1 ; i-- ) {
        st = 0;
        dr = n + 1;
        while( dr - st > 1 ) {
            mij = ( st + dr ) / 2;
            if( mij - query( mij ) < v[i] )
                st = mij;
            else
                dr = mij;
        }
        ans[dr] = i;
        update( dr );
    }
    for( i = 1 ; i <= n ; i++ )
        cout << ans[i] << '\n';
    return 0;
}