Cod sursa(job #1606382)

Utilizator aaron72Armand Ioan Anusca Popa aaron72 Data 20 februarie 2016 10:50:34
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>
#define nmax 30005
using namespace std;

int a[nmax],aib[nmax],n,t[nmax];

inline void Update(int p,int x)
{
    while(p<=n)
    {
        aib[p]+=x;
        p+=(p&(-p));
    }
}

inline int Query(int p)
{
    int val=0;
    while(p>0)
    {
        val+=aib[p];
        p-=(p&(-p));
    }
    return val;
}

inline int Bin_Search(int x)
{
    int sol=-1,mij,st=1,dr=n,inter;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        inter=Query(mij);
        if(inter==x)
        {
            sol=mij;
            dr=mij-1;
        }
        else if(inter>x) dr=mij-1;
        else st=mij+1;
    }
    return sol;
}

inline void Solve()
{
    int i,poz;
    for(i=1;i<=n;i++)
        Update(i,1);
    for(i=n;i>0;i--)
    {
        poz=Bin_Search(a[i]);
        t[poz]=i;
        Update(poz,-1);
    }
    ofstream fout("schi.out");
    for(i=1;i<=n;i++)
        fout<<t[i]<<"\n";
    fout.close();
}

inline void Input()
{
    int i;
    ifstream fin("schi.in");
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>a[i];
    fin.close();
}

int main()
{
    Input();
    Solve();
    return 0;
}