Cod sursa(job #3323098)

Utilizator StonkDavid Andrei Mateis Stonk Data 17 noiembrie 2025 00:39:57
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <iostream>

using namespace std;

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

int schiori[30001];
int pos[30001];

int aib[60001];

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

void bump(int pos) {
  for(int i = pos; i <= 1 << 15; i+= lsb(i)){
    aib[i]++;
  }
}

void debug_aib(){
  for(int i = 1; i <= 32; i++)
    cout << i << ": " << aib[i] << " \n";
}

int cb(int pozitii){
  int pos = 1 << 16;
  int pas;
  int amiesit = false;
  for(pas = 1 << 15; pas >= 1; pas /= 2){
    pos -= pas;
    //cout << pos - aib[pos] << '\n';
    if(pos - aib[pos] < pozitii){
      amiesit = true;
      break;
    }
  }
  if(!amiesit){
    return 1;
  }
  int sum = aib[pos];
  //cout << "am iesit din prima faza la" << pos << '\n';
  pas /= 2;  
  while(pas > 0){
    //cout << "vreau sa fac pasul la " << pos + pas << " si inainte am " << sum + aib[pos+pas] << '\n';
    //cout << sum << '\n';
    if(pos + pas - (sum + aib[pos + pas]) < pozitii){
      //cout << "am facut pasul " << aib[pos + pas] << '\n';
      sum += aib[pos + pas];
      pos += pas;
      //cout << "suma noua " << sum << '\n';
    }
    pas /= 2;
  }

  return pos + 1;
}

int main() {
  int n;
  fin >> n;
  /*
  bump(4);
  
  bump(7);
  cout << '\n' << cb(n) << '\n';
  debug_aib();
  */
  
  for(int i = 1; i <= n; i++){
    fin >> schiori[i];
    
  }

  for(int i = n; i > 0; i--){
    int schior = i;
    int position = cb(schiori[i]);
  
    pos[position] = schior;
    bump(position);

    //cout << "pentru schiorul " << i << " pozitia " << position << '\n';
    
  }

  for(int i = 1; i <= n; i++){
    fout << pos[i] << '\n';
  }
  return 0;
    
}