Cod sursa(job #2669705)

Utilizator NanuGrancea Alexandru Nanu Data 7 noiembrie 2020 17:24:38
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

#define Ub(x) (x & (-x))
#define NMAX 30001

int n, aib[NMAX], v[NMAX], ans[NMAX], i;

void scad(int pos) {
    for(int i = pos; i <= n; i += Ub(i))
        aib[i]--;
}

int suma(int pos) {
    int s = 0;
    for(int i = pos; i >= 1; i -= Ub(i))
        s += aib[i];
    return s;
}

int cautBinar(int x) {  //caut pozitia care are fix x locuri libere
    int st = 1, dr = n, poz = NMAX; //caut cea mai din stanga pozitie;
    while(st <= dr) {
        int mid = (st + dr) / 2;
        int sum = suma(mid);
        if(sum == x && mid < poz)
            poz = mid;
        else if(x <= sum)
            dr = mid - 1;
        else st = mid + 1;
    }
    return poz;
}

int main() {
    cin >> n;
    for(i = 1; i <= n; i++)
        cin >> v[i];

    for(int i = 1; i <= n; i++)
        aib[i] = Ub(i);   //retin cate pozitii am libere pana la fiecare element
    
    for(i = n; i >= 1; i--) {
        int poz = cautBinar(v[i]);
        ans[poz] = i;
        scad(poz);
    }

    for(i = 1; i <= n; i++)
        cout << ans[i] << '\n';

    return 0;
}