Cod sursa(job #2701236)

Utilizator marcumihaiMarcu Mihai marcumihai Data 30 ianuarie 2021 10:45:45
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f ("schi.in");
ofstream g ("schi.out");
int loc[100005];
int rasp[100005];
int ordine[100005];
int AIB[100005];
int n;
void update(int poz,int x)
{
    int i=poz;
    while(i<=n)
    {
        AIB[i]+=x;
        i+=(i & (-i));
    }
}
int query(int poz)
{
    int i=poz;
    int val=0;
    while(i>0)
    {
        val+=AIB[i];
        i-=(i & (-i));
    }
    return val;
}
int bs(int x)
{
    int st=1;
    int dr=n;
    int mij=(st+dr)/2;
    int sol=-1;
    while(st<=dr)
    {
        int val=query(mij);
        if(val==x)
        {
            sol = mij;
            dr = mij-1;
        }
        else if(val>x)
            dr=mij-1;
        else
            st=mij+1;

        mij=(st+dr)/2;
    }
    return sol;
}
int main()
{
    f>>n;
    for(int i=1; i<=n; ++i)
        f>>loc[i];
    for(int i=1;i<=n;i++)
        update(i,1);
    for(int i=n; i>0; --i)
    {
        int x=bs(loc[i]);
        rasp[x]=i;
        update(x,-1);
    }
    for(int i=1; i<=n; ++i)
        g<<rasp[i]<<"\n";

    return 0;
}