Cod sursa(job #2952625)

Utilizator NanuGrancea Alexandru Nanu Data 9 decembrie 2022 16:51:13
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

#define DIM 30000
#define Ub(x) (x & -x)

int n;
int aib[DIM + 5], v[DIM + 5], sol[DIM + 5];

static inline void Add(int poz, int val) {
  for(int i = poz; i <= n; i += Ub(i))
    aib[i] += val;
}

static inline int Suma(int poz) {
  int s = 0;
  for(int i = poz; i >= 1; i -= Ub(i))
    s += aib[i];

  return s;
}

static inline int CautBinarSt(int x) {  //caut pozitia care are fix x locuri libere
    int st = 1, dr = n, poz = DIM + 5; //caut cea mai din stanga pozitie;
    while(st <= dr) {
        int mid = (st + dr) / 2;
        int sum = Suma(mid);
        if(sum == x && mid < poz)
            poz = mid;
        else if(x <= sum)
            dr = mid - 1;
        else st = mid + 1;
    }
    return poz;
}

int main() {
  fin >> n;
  for(int i = 1; i <= n; i++) 
    fin >> v[i];
  
  for(int i = 1; i <= n; i++)
    aib[i] = Ub(i);
  
  //parcurg de la coada pentru ca ultimul concurent are pozitia exacata
  for(int i = n; i >= 1; i--) {
    int p = CautBinarSt(v[i]);
    sol[p] = i;
    Add(p, -1); //mai ocup un loc;
  }

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

  return 0;
}