Cod sursa(job #2791544)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 30 octombrie 2021 18:02:34
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 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 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 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;
}