Cod sursa(job #2091555)

Utilizator MoodyFaresFares Mohamad MoodyFares Data 19 decembrie 2017 20:38:24
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#define terminal0(x) x & -x

using namespace std;

const int MAX_N = 30000;

int n;
int a[1 + MAX_N];
int aib[1 + MAX_N];
int sol[1 + MAX_N];

void update(int poz, int val) {
  for (int i = poz; i <= n; i += terminal0(i)) {
    aib[i] += val;
  }
}

int query(int poz) {
  int ans = 0;
  for (int i = poz; i >= 1; i -= terminal0(i)) {
    ans += aib[i];
  }
  return ans;
}

int main() {
  ifstream cin("schi.in");
  ofstream cout("schi.out");
  
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    update(i, 1);
  }
  for (int i = n; i >= 1; i--) {
    int left, right;
    left = 1;
    right = n;
    int last = 1;
    while (left <= right) {
      int med = (left + right) / 2;
      if (query(med) >= a[i]) {
        last = med;
        right = med - 1;
      } else {
        left = med + 1;
      }
    }
    sol[last] = i;
    update(last, -1);
  }
  for (int i = 1; i <= n; i++) {
    cout << sol[i] << '\n';
  }
  return 0;
}