Cod sursa(job #1357031)

Utilizator juniorOvidiu Rosca junior Data 23 februarie 2015 18:34:09
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <iostream>

using namespace std;

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

int n, i, pi, p;
int Arb[dim], a[dim], c[dim];
ifstream fin("schi.in");
ofstream fout("schi.out");

void Adauga(int p, int v) {
  int i;
  for (i = p; i <= n; i += p2(i))
    Arb[i] += v;
}

int Cauta(int v) {
  int i, p = pi;
  for (i = 0; p; p >>= 1)
    if (i + p <= n)
      if (Arb[i + p] < v) {
        i += p, v -= Arb[i];
        if (v == 0)
          return i;
      }
  return i + 1;
}

int main() {
  fin >> n;
  for (i = 1; i <= n; i++) {
    fin >> a[i];
    Adauga(i, 1);
  }
  for (pi = 1; pi < n; pi <<= 1); // pasul initial pentru cautare
  for (i = n; i >= 1; i--) {
    p = Cauta(a[i]); // pozitia pana la care avem suma a[i]
    c[p] = i; // concurentul i va fi pe pozitia p in clasamentul final
    Adauga(p, -1);
  }
  for (i = 1; i <= n; i++)
    fout << c[i] << '\n';
}