Cod sursa(job #2105870)

Utilizator daniela12Sandu Daniela Teodora daniela12 Data 14 ianuarie 2018 14:53:41
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int v[30005],n, t[30005], fi[30005];
void update(int k)
{
    int i;
    for(i=k;i<=n;i+=(i&-i))
        t[i]--;
}
int query(int k)
{
    int x=0, i;
    for(i=k;i>=1;i-=(i&-i))
        x+=t[i];
    return x;
}
int cautareBin (int st, int dr, int k)
{
    int m;
    while(st<=dr)
    {
        m=(st+dr)>>1;
        int libere=query(m);
        if(libere<k)
            st=m+1;
        else
            dr=m-1;
    }
    update(dr+1);
    return dr+1;
}
int main()
{
    int i, j;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    f.close();
    for(i=1;i<=n;i++)
        t[i]=(i&-i);
    for(i=n;i>=1;i--)
    {
        j=cautareBin(1, n, v[i]);
        fi[j]=i;
    }
    for(i=1;i<=n;i++)
        g<<fi[i]<<'\n';
    g.close();
}