Cod sursa(job #3247916)

Utilizator IanisBelu Ianis Ianis Data 9 octombrie 2024 20:03:26
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 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;
   }
}

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

/*
................................
# # # # # # # # # # # # # # # #
##  ##  ##  ##  ##  ##  ##  ##  
####    ####    ####    ####    
########        ########
################
################################
*/

int bs(int x) {
   int mask = 0, sum = 0;
   
   for (int i = 15; i >= 0; i--) {
      if ((mask | (1 << i)) > n) continue;
      mask |= 1 << i;
      sum += aib[mask];
      if (mask > n || sum >= x) {
         sum -= aib[mask];
         mask ^= 1 << i;
      }
   }
   
   return mask + 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;
}