Cod sursa(job #1606381)

Utilizator ciocan_catalinCiocan Catalin - Iulian ciocan_catalin Data 20 februarie 2016 10:49:44
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
const int nmax = 30005;
int n,aib[nmax],v[nmax],t[nmax];

void Read()
{
    fin>>n;
    for(int i = 1; i <= n; i++) fin>>v[i];
}

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

inline int Query(int p)
{
    int s = 0;
    while(p > 0)
    {
        s+=aib[p];
        p -= (p&(-p));
    }
    return s;
}
inline int Search(int x)
{
    int sol,st,dr,mid,val;
    sol = -1;
    st = 1, dr = n;
    while(st <= dr)
    {
        mid = (st+dr)/2;
        val = Query(mid);
        if(val==x)
        {
            sol = mid;
            dr = mid-1;
        }
        else if(val > x) dr = mid-1;
        else st = mid+1;
    }
    return sol;
}

void Solve()
{
    int i,p;
    for(i = 1; i <= n; i++) Update(i,1);
    for(i = n; i > 0; i--)
    {
        p = Search(v[i]);
        t[p] = i;
        Update(p,-1);
    }
    for(i = 1; i <= n; i++)
        fout<<t[i]<<"\n";
}


int main()
{
    Read();
    Solve();
    fout.close();
    return 0;
}