Cod sursa(job #1355758)

Utilizator juniorOvidiu Rosca junior Data 22 februarie 2015 22:49:03
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 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 Suma(int p) { // suma pana la pozitia p
  int i, s = 0;
  for (i = p; i > 0; i -= p2(i))
    s += Arb[i];
  return s;
}

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 (int j = 1; j <= n; j++) {
      cout << Suma(j) - Suma(j - 1) << ' ';
    }
    cout << endl;*/
  }
  for (i = 1; i <= n; i++)
    fout << c[i] << '\n';
}

/*
8
1
1
3
4
4
2
1
3
----------------
1
2 1
2 1 3
2 1 3 4
2 1 3 5 4
2 6 1 3 5 4
7 2 6 1 3 5 4
7 2 8 6 1 3 5 4
*/