Cod sursa(job #2314698)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 8 ianuarie 2019 23:04:37
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <fstream>
using namespace std;
#define N 30300

inline int zeros (int x){
    return x & (-x);
}

int aib[N],i,n,v[N],ans[N],k;

void update (int poz, int x){
    for (int i = poz; i < n; i += zeros(i))
        aib[i] += x;
}

int compute (int poz) {
    int ans = 0;
    for (int i = poz; i > 0; i -= zeros(i))
        ans += aib[i];
    return ans;
}

int bs (int val) {
    int poz = 0;
    for (int i = n - 1; i > 0; i >>=1)
        while (poz + i < n && compute(poz + i) < val)
        poz += i;
    return poz + 1;
}
int main()
{
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    fin >> n;
    ++n;
    for (i = 1; i < n; ++i){
        fin >> v[i];
        aib[i] = zeros(i);
    }
    for (i = n - 1; i > 0; --i){
        k = bs(v[i]);
        ans[k] = i;
        update(k, -1);
    }
    for (i = 1; i < n; ++i)
        fout << ans[i] << '\n';
    fin.close();
    fout.close();
    return 0;
}