Cod sursa(job #757646)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 12 iunie 2012 20:50:08
Problema Schi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#define N 30010

using namespace std;

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

int n,i,AIB[N],lsb[N],ANS[N],V[N];

void Update (int p)
{
    for (;p<=n;p+=lsb[p]) AIB[p]++;
}

int Query (int p)
{
    int v=0;
    for (;p>=1;p-=lsb[p]) v+=AIB[p];
    return v;
}

void Search (int i, int v)
{
    int p=1,u=n,m,x;
    while (p<=u)
    {
        m=(p+u)/2;
        x=m-Query(m);
        if (x==v && ANS[m]==0)
        {
            ANS[m]=i;
            Update(m);
            return;
        }
        if (x==v && ANS[m]!=0)
        {
            u=m-1;
            continue;
        }
        if (x<v) p=m+1;
            else u=m-1;
    }
}

int main ()
{
    f >> n;
    for (i=1;i<=n;i++)
    {
        f >> V[i];
        lsb[i]=i&(-i);
    }

    Update(V[n]);ANS[V[n]]=n;
    for (i=n-1;i>=1;i--)
        Search(i,V[i]);

    for (i=1;i<=n;i++)
        g << ANS[i] << '\n';
    f.close();g.close();
    return 0;
}