Cod sursa(job #2762321)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 6 iulie 2021 15:04:44
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>

using namespace std;

const int Nmax = 30000;
int aib[Nmax + 1], a[Nmax + 1], sol[Nmax + 1];

void upd(int k, int n)
{
    while (k <= n)
    {
        aib[k]--;
        k += (k & -k);
    }
}

int qry(int k)
{
    int ans = 0;
    while (k >= 1)
    {
        ans += aib[k];
        k -= (k & -k);
    }
    return ans;
}

int cb(int x, int n)
{
    int st = 1, dr = n, ans = 30001;
    while (st <= dr)
    {
        int mijl = (st + dr) / 2;
        int s = qry(mijl);
        if (s == x && mijl < ans)
        {
            ans = mijl;
        }
        else if (s >= x)
        {
            dr = mijl - 1;
        }
        else
        {
            st = mijl + 1;
        }
    }
    return ans;
}

int main()
{
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    int n;
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> a[i];
        aib[i] = (i & -i);
    }
    for (int i = n; i >= 1; i--)
    {
        int x = cb(a[i], n);
        sol[x] = i;
        upd(x, n);
    }
    for (int i = 1; i <= n; i++)
    {
        fout << sol[i] << "\n";
    }
    return 0;
}