Cod sursa(job #2038565)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 13 octombrie 2017 20:00:04
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<fstream>
using namespace std;
ifstream fi("schi.in");
ofstream fo("schi.out");
int F[30001];
int n,i,A[30001],p,R[30001];

void update(int poz, int x)
{
    while(poz<=n)
    {
        F[poz]+=x;
        poz=poz+(poz&(poz^(poz-1)));
        //poz&(-poz)
    }
}

int f(int poz)
{
    int sum=0;
    while(poz>=1)
    {
        sum+=F[poz];
        poz=poz-(poz&(poz^(poz-1)));
    }
    return sum;
}

int query(int x, int y)
{
    return f(y)-f(x-1);
}

int bs(int st, int dr, int val)
{
    int mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(query(1,mij)<val)
            st=mij+1;
        else
            dr=mij-1;
    }
    return st;
}

int main()
{
    fi>>n;
    for(i=1; i<=n; i++)
    {
        fi>>A[i];
        update(i,1);
    }
    for(i=n; i>=1; i--)
    {
        p=bs(1,n,A[i]);
        update(p,-1);
        R[p]=i;
    }
    for(i=1; i<=n; i++)
        fo<<R[i]<<"\n";
    fi.close();
    fo.close();
    return 0;
}