Cod sursa(job #3264313)

Utilizator adelina_15InfoAdelina Radoi adelina_15Info Data 20 decembrie 2024 12:31:23
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;
vector<int> v;
int aib[80000];
int rez[40000];

void Adauga(int poz, int val)
{
    while(poz <= n)
    {
        aib[poz] += val;
        poz += (poz&(-poz));
    }
}

int Sum(int poz)
{
    int suma = 0;
    while(poz > 0)
    {
        suma += aib[poz];
        poz -= (poz&(-poz));
    }
    return suma;
}

int CautaBin(int x)
{
    int step = 1;
    while(step < n)
        step <<= 1;
    int i;
    for(i = 0; step; step >>= 1)
        if(i+step <= n && Sum(i+step) < x)
            i += step;

    return i+1;
}

int main()
{
    fin >> n;
    v.resize(n+1);
    for(int i = 1; i <= n; i++)
    {
        fin >> v[i];
        Adauga(i, 1);
    }
    for(int i = n; i > 0; i--)
    {
        int poz = CautaBin(v[i]);
        Adauga(poz, -1);
        rez[poz] = i;
    }
    for(int i = 1; i <= n; i++)
        fout << rez[i] << "\n";
    return 0;
}