Cod sursa(job #1747377)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 24 august 2016 20:27:53
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#define VAL 30005
#define INTR 65536

using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

int N, i, p[VAL];
int v[VAL], poz;
int aint[INTR], s;

void initializare(int nod, int st, int dr)
{
    if (st==dr)
      aint[nod]=1;
    else
    {
        int mij=(st+dr) / 2;
        initializare(2*nod, st, mij);
        initializare(2*nod+1, mij+1, dr);
        aint[nod]=aint[2*nod]+aint[2*nod+1];
    }
}

void update(int nod, int st, int dr, int poz)
{
    if (st==dr)
      aint[nod]--;
    else
    {
        int mij=(st+dr) / 2;
        if (poz<=mij)
          update(2*nod, st, mij, poz);
        else
          update(2*nod+1, mij+1, dr, poz);
        aint[nod]=aint[2*nod]+aint[2*nod+1];
    }
}

int query(int nod, int st, int dr, int sum)
{
    if (st==dr)
      return st;
    else
    {
        int mij=(st+dr) / 2;
        if (s+aint[2*nod]<sum)
        {
            s+=aint[2*nod];
            query(2*nod+1, mij+1, dr, sum);
        }
        else
          query(2*nod, st, mij, sum);
    }
}

int main()
{
    fin >> N;
    for (i=1; i<=N; i++)
      fin >> p[i];
    initializare(1, 1, N);
    for (i=N; i>=1; i--)
    {
        s=0;
        poz=query(1, 1, N, p[i]);
        v[poz]=i;
        update(1, 1, N, poz);
    }
    for (i=1; i<=N; i++)
      fout << v[i] << '\n';
    fin.close();
    fout.close();
    return 0;
}