Cod sursa(job #2924193)

Utilizator db_123Balaban David db_123 Data 26 septembrie 2022 20:16:44
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

class Fenwick {
private:
    int n;
    vector<int> bit;
    void update(int node,int val) {
        int ix=node;
        while(ix<=n) {
            bit[ix]+=val;
            ix+=(ix & (~ix+1));
        }
    }
    int query(int node) {
        int ix=node,sum=0;
        while(ix>0) {
            sum+=bit[ix];
            ix-=(ix & (~ix+1));
        }
        return sum;
    }
public:
    void resize(int n) {
        this->n=n;
        bit.resize(n+1);
    }
    void update(int l,int r,int val) {
        update(l,val);
        update(r+1,-val);
    }
    int query(int l,int r) {
        return query(r)-query(l-1);
    }
};

int n;
vector<int> v;
Fenwick aib;

void read() {
    cin>>n;
    v.resize(n+1);
    for(int i=1;i<=n;i++) {
        cin>>v[i];
    }
}

int bs(int val) {
    int l=1,r=n,mid,res=-1;
    while(l<=r) {
        mid=l+(r-l)/2;
        int nr=aib.query(1,mid);
        if(nr==val) {
            res=mid;
            r=mid-1;
        }
        else if(nr>val) {
            r=mid-1;
        }
        else {
            l=mid+1;
        }
    }
    return res;
}

void solve() {
    aib.resize(n);
    for(int i=1;i<=n;i++) {
        aib.update(i,n,1);
    }
    // cout<<bs(1)<<"\n";
    // for(int i=1;i<=n;i++) {
    //     cout<<aib.query(1,i)<<" ";
    // }
    // cout<<"\n";
    int pos;
    vector<int> res(n+1);
    for(int i=n;i>0;i--) {
        pos=bs(v[i]);
        if(pos>-1) {
            res[pos]=i;
            aib.update(pos,n,-1);
        }
    }
    for(int i=1;i<=n;i++) {
        cout<<res[i]<<"\n";
    }
}

int main() {
    
    read();
    solve();
    return 0;
}