Cod sursa(job #1094098)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 28 ianuarie 2014 21:40:50
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#define dmax 30001
using namespace std;

FILE *f=fopen("schi.in", "r");
FILE *g=fopen("schi.out", "w");

int v[4*dmax],n, p[dmax], pf[dmax];
int sum;

void update(int val, int poz,int a, int b, int nod)
{
    if(a==b)
        v[nod]=v[nod]+val;
    else
    {
        int m=(a+b)/2;
        if(poz>m) update(val,poz,m+1,b,2*nod+1);
        else update(val,poz,a,m,2*nod);
        v[nod]=v[2*nod]+v[2*nod+1];
    }

}

void read()
{
    fscanf(f, "%i", &n);
    for(int i=1; i<=n; i++)
    {
        fscanf(f, "%i", &p[i]);
        update(1,i,1,n,1);
    }
}


int querry(int val, int st, int dr, int nod)
{
    if(st==dr)
        return st;
    else
    {
        int m=(st+dr)/2;
        if(sum+v[2*nod]>=val)
            return querry(val, st, m, 2*nod);
        else
        {
            sum=sum+v[2*nod];
            return querry(val,m+1,dr, 2*nod+1);
        }
    }

}

int main()
{
    read();
    for(int i=n; i>0; i--)
    {
        sum=0;
        int a=querry(p[i],1,n,1);
        pf[a]=i;
        update(-1,a,1,n,1);
    }
    for(int i=1; i<=n; i++)
        fprintf(g,"%i%c",pf[i], '\n');
    return 0;
}