Cod sursa(job #2791562)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 30 octombrie 2021 18:49:05
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 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;
int queries[1 + NMAX];
int ans[1 + NMAX];

int biTree[2 * NMAX];

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 i, step;
  int ans = -1;
  for (step = 1; step < n; step <<= 1);

  for (i = 0; step; step >>= 1) {
    if (biTree[i + step] == target)
      ans = i + step;
    else if (biTree[i + step] < target) {
      i += step;
      target -= biTree[i];
    }
  }

  return ans;
}

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

  in >> 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;
}