Cod sursa(job #2046456)

Utilizator alexandruilieAlex Ilie alexandruilie Data 23 octombrie 2017 20:17:38
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>

using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n,aib[30001],v[30001],rasp,clasament[30001];
void adun(int x,int val)
{
    int i;
    for( i=x;i<=n;i+=i&(-i))
        aib[i]+=val;
}
int suma(int x)
{
    int s=0,i;
    for(i=x;i>=1;i-=i&(-i))
        s+=aib[i];
    return s;
}
int cautbinar(int st,int dr,int x)
{
    int minim=n+1;
    if(x==1&&aib[4]==1)
        x=1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        int sum=suma(mid);
        if(sum==x&&mid<minim) minim=mid;
        else if(sum>=x) dr=mid-1;
        else st=mid+1;
    }

    return minim;
}
int main()
{
    f>>n;
    int i;
    for(i=1;i<=n;i++) f>>v[i];
    for(i=1;i<=n;i++) aib[i]=i&(-i);
    for(i=n;i>=1;i--)
    {
        rasp=cautbinar(1,n,v[i]);
        adun(rasp,-1);
        clasament[rasp]=i;
    }
    for(i=1;i<=n;i++) g<<clasament[i]<<'\n';
    return 0;
}