Cod sursa(job #3299278)

Utilizator 2016Teo@Balan 2016 Data 5 iunie 2025 10:54:00
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
using namespace std;

const int NMAX = 30005;
int aib[NMAX], sol[NMAX];

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

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

int find_kth(int k, int n) {
  int pos = 0;
  for(int step = 1 << 15; step; step >>= 1) {
    if(pos + step <= n && aib[pos + step] < k) {
      k -= aib[pos + step];
      pos += step;
    }
  }
  return pos + 1;
}

int main() {
  ifstream in("schi.in");
  ofstream out("schi.out");

  int n, x;
  in >> n;

  for(int i = 1; i <= n; ++i)
    update(i, 1, n);

  for(int i = n; i >= 1; --i) {
    in >> x;
    int pos = find_kth(x, n); 
    sol[pos] = i;             
    update(pos, -1, n);      
  }

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

  return 0;
}