Cod sursa(job #2165803)

Utilizator futurengineerOana Rosca futurengineer Data 13 martie 2018 13:43:38
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>

#define p2(x) (x ^ (x-1)) & x

using namespace std;

int n, l[50001], arb[50001], sol[50001], npoz;

void adauga(int poz, int val) {
  for (int i = poz; i <= n; i += p2(i))
    arb[i] += val;
}

int sum(int poz) {
  int s = 0;
  for (int i = poz; i > 0; i -= p2(i))
    s += arb[i];
  return s;
}

int cautbin(int poz) {
  int npoz, st = 1, dr = n, m;
  while (st <= dr) {
    m = (st+dr)/2;
    int suma = sum(m);
    if (suma == poz)
      npoz = m, dr = m-1;
    else
      if (suma < poz)
        st = m+1;
      else
        dr = m-1;
  }
  return npoz;
}

int main () {
  ifstream fi("schi.in");
  ofstream fo("schi.out");
  fi >> n;
  for (int i = 1; i <= n; i++)
    fi >> l[i], adauga(i, 1);
  for (int i = n; i >= 1; i--) {
    npoz = cautbin(l[i]);
    sol[npoz] = i;
    adauga(npoz, -1);
  }
  for (int i = 1; i <= n; i++)
    fo << sol[i] << '\n';
  return 0;
}