Cod sursa(job #2116657)

Utilizator armigheGheorghe Liviu Armand armighe Data 27 ianuarie 2018 20:24:12
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<cstdio>
#include<fstream>
using namespace std;
FILE *f=fopen("schi.in","r");
ofstream g("schi.out");
int n,arbint[120002],v[30002],sol[30002];
void init(int nod, int st, int dr) {
  if (st == dr) {
    arbint[nod] = 1;
  } else {
    int mij = (st + dr) / 2;
    init(2 * nod, st, mij) ;
    init(2 * nod + 1, mij + 1, dr);
    arbint[nod] = arbint[2 * nod] + arbint[2 * nod + 1];
  }
}

void init() {
  init(1, 1, n);
}

int queryKth(int nod, int st, int dr, int k) {
  if (st == dr) {
    return st;
  } else {
    int mij = (st + dr) / 2;
    if (k <= arbint[2 * nod])
      return queryKth(2 * nod, st, mij, k);
    else
      return queryKth(2 * nod + 1, mij + 1, dr, k - arbint[2 * nod]);
  }
}

int queryKth(int k) {
  return queryKth(1, 1, n, k);
}

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

void update(int index, int newValue) {
  update(1, 1, n, index, newValue);
}


int main()
{
    int i,x;
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(f,"%d",&v[i]);
    init();
    for(i=n;i>=1;i--)
    {
        x=queryKth(v[i]);
        sol[x]=i;
        update(x,0);
    }
    for(i=1;i<=n;i++)
        g<<sol[i]<<'\n';
    return 0;
}