Cod sursa(job #3247906)

Utilizator IanisBelu Ianis Ianis Data 9 octombrie 2024 19:42:49
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
ifstream fin("schi.in");
ofstream fout("schi.out");
#define endl '\n'
#endif

#define lsb(x) (x & (-x))

const int NMAX = 3e4+5;

int n;
int a[NMAX];
int ans[NMAX];
int aib[NMAX];

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

int query(int pos) {
   int sum = 0;
   for (int i = pos; i >= 1; i -= lsb(i)) {
      sum += aib[i];
   }
   return sum;
}

void read() {
   fin >> n;
   for (int i = 1; i <= n; i++) {
      fin >> a[i];
   }
}

int bs(int x) {
   int l = 1, r = n;
   
   while (l <= r) {
      int mid = (l + r) >> 1;
      if (query(mid) < x) {
         l = mid + 1;
      } else {
         r = mid - 1;
      }
   }
   
   return r + 1;
}

void solve() {
   for (int i = 1; i <= n; i++) {
      update(i, 1);
   }

   for (int i = n; i >= 1; i--) {
      int pos = bs(a[i]);
      update(pos, -1);
      ans[pos] = i;
   }

   for (int i = 1; i <= n; i++) {
      fout << ans[i] << endl;
   }
}

signed main() {
   read();
   solve();
   return 0;
}