Cod sursa(job #2127408)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 10 februarie 2018 17:07:41
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 30000;

int n, a[MAXN + 1], aib[MAXN + 1], t[MAXN + 1];

void Update(int p, int x) {
  while(p <= n) {
    aib[p] += x;
    p += (p&(-p));
  }
}

int Query(int p) {
  int s = 0;
  while(p > 0) {
    s += aib[p];
    p -= (p&(-p));
  }
  return s;
}

int CautBin(int x) {
  int st, dr, mij, s, poz;
  st = 1;
  dr = n;
  while(st <= dr) {
    mij = (st + dr) / 2;
    s = Query(mij);
    if(s == x) {
      poz = mij;
      dr = mij - 1;
    }
    else if(s > x)
      dr = mij - 1;
    else
      st = mij + 1;
  }
  return  poz;
}

int main() {
  FILE *fin, *fout;
  int i, x;
  fin = fopen ("schi.in", "r");
  fout = fopen ("schi.out", "w");
  fscanf (fin, "%d", &x);
  for(i = 1; i <= n; i++) {
    fscanf (fin, "%d", &a[i]);
    Update(i,1);
  }
  for(i = n; i >= 1; i--) {
    x = CautBin(a[i]);
    t[x] = i;
    Update(x,-1);
  }
  for(i = 1; i <= n; i++)
    fprintf (fout, "%d\n", t[i]);
  fclose (fin);
  fclose (fout);
  return 0;
}