Cod sursa(job #2836910)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 21 ianuarie 2022 09:41:14
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#define NMAX 100000
#define LOG 17
using namespace std;

int a[NMAX + 1];
int b[NMAX + 1];
int v[NMAX + 1];
int n, t;

int lsb (int x){

  return x & (-x);
}

/*void build (){

  for (int i = 1; i <= n; i++){
    a[i] += v[i];

    if (i + lsb(i) <= n)
      a[i + lsb(i)] += a[i];
  }
}*/

void update (int poz, int val){

  while (poz <= n){
    a[poz] += val;
    poz += lsb(poz);
  }

}

int sum (int poz){
  int s = 0;
  while (poz > 0){
    s += a[poz];
    poz -= lsb(poz);
  }

  return s;
}

int bs(int val){
    int st = 1;
    int dr = n;
    while(st <= dr){

      int mid = (st + dr) / 2;
      if (sum (mid) >= val){
        dr = mid - 1;
      }
      else{
        st = mid + 1;
      }
    }

    return st;
}

int main(){

  ifstream fin ("schi.in");
  ofstream fout ("schi.out");
  int sol;
  fin >> n;
  for(int i = 1;i <= n;i++){
    fin >> v[i];
    update(i ,1);
  }

  for (int i = n; i >= 1; i--){
    sol = bs (v[i]);
    update(sol, -1);
    b[sol] = i;

  }
  for(int i = 1; i <= n; i++){
    fout << b[i] << "\n";
  }
  return 0;
}