Cod sursa(job #2019651)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 8 septembrie 2017 11:26:40
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>

#define ub(x) (x&(x-1))

using namespace std;

ifstream f("schi.in");
ofstream g("schi.out");

int AIB[30005],S,i,j,sol[30005],n,m,a[30005],poz;

void dif (int x)
{
    for(j=x; j<=n; j+=ub(j))
        AIB[j]--;
}

int sum (int poz)
{
    int S=0;
    for(j=poz; j>0; j-=ub(j))
        S+=AIB[j];
    return S;
}


int cautare (int x)
{
    int st=1;
    int dr=n;
    int poz=0;
    int Min=30005;
    while(st<=dr&&!poz)
    {
        m=(st+dr)/2;
        if(sum(m)==x&&m<Min)
        {
            poz=m;
            Min=m;
        }
        else if(sum(m)>x)
            dr=m-1;
        else st=m+1;
    }
    return Min;
}

int main()
{
    f>>n;
    for(i=1; i<=n; i++)
        f>>a[i];
    for(i=n; i>=1; i--)
    {
        poz=cautare(a[i]);
        sol[poz]=i;
        dif(poz);
    }
    for(i=1; i<=n; i++)
        g<<sol[i]<<'\n';
    return 0;
}