Cod sursa(job #2702454)

Utilizator KPP17Popescu Paul KPP17 Data 4 februarie 2021 08:34:56
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
#define mF "schi"
std::ifstream in(mF ".in");
std::ofstream out(mF ".out");
const int N = 30001;
int n, i, I[N], V[N], R[N];
int S(int i) {int s = 0; do s += V[i]; while (i ^= i & -i); return s;}
int Q(int s) {int i = 1, j = n, m; while (i <= j) if (S(m = i+j>>1) < s) i = m+1; else j = m-1; return i;}
void U(int i) {do V[i]--; while (i += i & -i, i <= n);}
int main()
{
    in >> n;
    for (i = 1; i <= n; i++) {in >> I[i]; if (i+(i&-i) <= n) V[i + (i & -i)] += ++V[i]; else ++V[i];}
    for (i = n; i; i--) {int p = Q(I[i]); R[p] = i; U(p);}
    for (i = 1; i <= n; i++) out << R[i] << '\n';
}