Cod sursa(job #2791547)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 30 octombrie 2021 18:10:53
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <iostream>
#include <fstream>

#define inout(f) std::ifstream in((f) + (std::string) ".in");std::ofstream out((f) + (std::string) ".out")
#define d(x) std::cout << x << std::endl
#define dm(msg, x) std::cout << msg << x << std::endl

const int NMAX = 3e4;
const int LOGMAX = 15;

int n, logN;
int queries[1 + NMAX];
int ans[1 + NMAX];

int biTree[2 * NMAX];

inline int bsLog2(int a) {
  int left = 0, right = LOGMAX, ans = -1;

  while (left <= right) {
    int mid = (left + right) / 2;

    if ((1 << mid) <= a) {
      ans = mid;
      left = mid + 1;
    }
    else
      right = mid - 1;
  }

  return ans;
}

inline int lsb(int a) {
  return a & -a;
}

void biTreeUpdate(int index, int value) {
  for (int i = index; i <= n; i += lsb(i))
    biTree[i] += value;
}

int biTreeQuery(int index) {
  int ans = 0;
  for (int i = index; i > 0; i -= lsb(i)) 
    ans += biTree[i];

  return ans;
}

// int biTreeSearch(int target) {
//   int index = 0, ans = -1;
//   for (int exp = logN; exp >= 0; --exp) {
//     if (biTree[index + (1 << exp)] < target)
//       index += (1 << exp), target -= biTree[index];
//     else if (biTree[index + (1 << exp)] == target)
//       ans = index + (1 << exp);
//   }

//   return ans;
// }

int biTreeSearch(int target) {
  int left = 1, right = n;
  int ans = -1;

  while (left <= right) {
    int mid = (left + right) / 2;

    if (biTreeQuery(mid) >= target)
      ans = mid, right = mid - 1;
    else
      left = mid + 1;
  }

  return ans;
}

int main() {
  inout("schi");

  in >> n;
  logN = bsLog2(n);
  for (int i = 1; i <= n; ++i) {
    in >> queries[i];

    biTreeUpdate(i, 1);
  }

  for (int i = n; i >= 1; --i) {
    int index = biTreeSearch(queries[i]);

    ans[index] = i;

    biTreeUpdate(index, -1);
  }

  for (int i = 1; i <= n; ++i)
    out << ans[i] << '\n';

  return 0;
}