Cod sursa(job #2021930)

Utilizator dragos231456Neghina Dragos dragos231456 Data 14 septembrie 2017 23:03:28
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#define zeros(x) ((x^(x-1))&x)
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n,aib[30005],a,v[30005],ans[30005],d;

void add(int x,int y)
{
    for(int i=x;i<=n;i+=zeros(i))
    {
        aib[i]+=y;
    }
}

int compute(int x)
{
    int rez=0;
    for(int i=x;i>0;i-=zeros(i))
    {
        rez+=aib[i];
    }
    return rez;
}

int poz(int x)
{
    int lt=0,md,rt=n;
    while(rt-lt!=1)
    {
        md=(lt+rt)/2;
        d=compute(md);
        if(d<x) lt=md;
        else if(d>=x) rt=md;
        else return md;
    }
    return rt;
}

int main()
{
    f>>n;
    for(int i=1;i<=n;++i)
    {
        add(i,1);
    }
    for(int i=1;i<=n;++i)
    {
        f>>v[i];
    }
    for(int i=n;i>=1;--i)
    {
        a=poz(v[i]);
        ans[a]=i;
        add(a,-1);
    }
    for(int i=1;i<=n;++i)
    {
        g<<ans[i]<<'\n';
    }
    return 0;
}