Cod sursa(job #757649)

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

using namespace std;

FILE* fin=fopen("schi.in","r");
FILE* fout=fopen("schi.out","w");
const int maxb=8192;
char buf[maxb];
int ptr=0;

inline int GetInt()
{
    int nr=0;
    while(buf[ptr]<'0'||'9'<buf[ptr])
        if (++ptr>=maxb) fread(buf,maxb,1,fin),ptr=0;
    while ('0'<=buf[ptr]&&buf[ptr]<='9')
    {
        nr=nr*10+buf[ptr]-'0';
        if (++ptr>=maxb) fread(buf,maxb,1,fin),ptr=0;
    }
    return nr;
}

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 ()
{
    n=GetInt();
    for (i=1;i<=n;i++)
    {
        V[i]=GetInt();
        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++)
        fprintf(fout,"%d\n",ANS[i]);
    fclose(fin);fclose(fout);
    return 0;
}