Cod sursa(job #2521031)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 10 ianuarie 2020 11:56:36
Problema Schi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
/**

varianta cu arbori de intervale

#include <iostream>
#include <cstdio>
#define NMAX 30000

using namespace std;

int n;
int v[NMAX + 5], aint[4 * NMAX + 5], ord[NMAX + 5];

void init(int nod, int st, int dr) {
  int mij = (st + dr) / 2;

  aint[nod] = dr - st + 1;
  if(dr != st) {
    init(2 * nod, st, mij);
    init(2 * nod + 1, mij + 1, dr);
  }
}

int query(int nod, int st, int dr, int qval) {
  int mij = (st + dr) / 2;

  aint[nod]--; /// update

  if(st == dr)
    return st;

  if(qval <= aint[2 * nod])
    return query(2 * nod, st, mij, qval);
  return query(2 * nod + 1, mij + 1, dr, qval - aint[2 * nod]);
}

int main() {
  freopen("schi.in", "r", stdin);
  freopen("schi.out", "w", stdout);
  int poz;

  scanf("%d", &n);
  for(int i = 1; i <= n; i++)
    scanf("%d", &v[i]);

  init(1, 1, n);
  for(int i = n; i >= 1; i--) {
    poz = query(1, 1, n, v[i]);
    ord[poz] = i;
  }

  for(int i = 1; i <= n; i++)
    printf("%d\n", ord[i]);

  return 0;
}

**/

/// varianta cu arbori indexati binar

#include <iostream>
#include <cstdio>
#define NMAX 30000

using namespace std;

int n, maxn;
int v[NMAX + 5], aib[2 * NMAX + 5], ord[NMAX + 5];

int lsb(int x) {
  return x & (-x);
}

int p2(int x) {
  return (x - lsb(x)) == 0;
}

void init() {
  int ni;

  maxn = n;
  while(!p2(maxn))
    maxn += lsb(maxn);

  for(int i = 1; i <= maxn; i++) {
    if(i <= n)
      aib[i]++;
    ni = i + lsb(i);
    aib[ni] += aib[i];
  }
}

int query(int nod, int val) {
  int b = lsb(nod), nnod = nod - b;

  b >>= 1;
  while(b) {
    nnod += b;
    if(val <= aib[nnod])
      return query(nnod, val);
    val -= aib[nnod];
    b >>= 1;
  }

  return nod;
}

void update(int poz) {
  aib[poz]--;
  poz += lsb(poz);
  if(poz <= maxn)
    update(poz);
}

int main() {
  freopen("schi.in", "r", stdin);
  freopen("schi.out", "w", stdout);
  int poz;

  scanf("%d", &n);
  for(int i = 1; i <= n; i++)
    scanf("%d", &v[i]);

  init();
  for(int i = n; i >= 1; i--) {
    poz = query(maxn, v[i]);
    ord[poz] = i;
    update(poz);
  }

  for(int i = 1; i <= n; i++)
    printf("%d\n", ord[i]);

  return 0;
}