Cod sursa(job #2014473)

Utilizator Y0da1NUME JMECHER Y0da1 Data 23 august 2017 19:01:18
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>

using namespace std;
int n;
int aib[30002], v[30002], fin[30002];

void update(int x, int val)
{
    for (int i = x; i<=n; i+=i&-i)
        aib[i]+=val;
}

int query(int x)
{
    int s=0;
    for (int i = x; i>0; i-=i&-i)
        s+=aib[i];
    return s;
}
int rangesum(int k)
{
    int st=1, dr=n, mij;
    while (st<dr)
    {
        mij=(st+dr)/2;
        //cout<<mij<<" ";
        if (query(mij)>=k)
            dr=mij;
        else
            st=mij+1;
    }
    if (query(mij)<k)
        ++mij;
    //cout<<mij<<" ";
    return mij;
}

int main()
{
    ifstream in ("schi.in");
    ofstream out ("schi.out");
    in >> n;
    int mid;
    for (int i = 1; i <= n; ++i)
    {
        in>>v[i];
        aib[i]=i&-i;
    }
    for (int i = n; i > 0; --i) //fin[i] - nr concurentului de pe locul i
    {
        mid = rangesum(v[i]);
        //cout<<mid<<"\n";
        fin[mid] = i;
        update(mid, -1);
    }
    for (int i = 1; i <= n; ++i)
        out<<fin[i]<<"\n";
}