Cod sursa(job #3302312)

Utilizator EricDimiCismaru Eric-Dimitrie EricDimi Data 6 iulie 2025 10:39:47
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>

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

const int MAX_N = 30'000;
const int MAX_LOG = (int)log2(MAX_N);

int aib[MAX_N + 1];
int loc[MAX_N + 1];
int sol[MAX_N + 1];
int n;

void update(int x, int y) {
   for (int i = x; i <= n; i += i & -i)
      aib[i] += y;
}

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

int binarySearch(int x) {
   // Cauta binar pe biti cea mai din stanga pozitia astfel incat SUM[1..pos] = x
   int pos = 0, sum = 0;
   for (int bit = MAX_LOG; bit >= 0; bit--)
      if ((pos | (1 << bit)) <= n && sum + aib[(pos | (1 << bit))] < x) {
         sum += aib[(pos | (1 << bit))];
         pos |= (1 << bit);
      }
   return pos + 1;
}

int main() {
   fin >> n;
   
   for (int i = 1; i <= n; i++) {
      fin >> loc[i];
      update(i, 1);   
   }
   
   for (int i = n; i >= 1; i--) {
      sol[binarySearch(loc[i])] = i;
      update(binarySearch(loc[i]), -1);
   }
   
   for (int i = 1; i <= n; i++)
      fout << sol[i] << "\n";
   
   fin.close();
   fout.close();
   return 0;
}