Cod sursa(job #2452676)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 31 august 2019 18:35:14
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>
#define NMAX 30000

using namespace std;

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

int ans[NMAX + 5], v[NMAX + 5], n, Sum[NMAX + 5];

void Update(int i, int j)
{
    for (int k = i; k <= n; k += (k ^ (k & (k - 1))))
        Sum[k] += j;
}

int Query(int i)
{
    int rez = 0;
    for (int k = i; k >= 1; k -= (k ^ (k & (k - 1))))
        rez += Sum[k];
    return rez;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i], Update(i, 1);
    for (int i = n; i >= 1; --i)
    {
        int st = 1, dr = n, sol = -1;
        while (st <= dr)
        {
            int mid = (st + dr) / 2;
            if (Query(mid) >= v[i])
            {
                sol = mid;
                dr = mid - 1;
            }
            else
            {
                st = mid + 1;
            }
        }
        Update(sol, -1);
        ans[sol] = i;
    }
    for (int i = 1; i <= n; ++i)
        fout << ans[i] << "\n";
    fin.close();
    fout.close();
    return 0;
}