Cod sursa(job #2753171)

Utilizator rapidu36Victor Manz rapidu36 Data 21 mai 2021 13:10:46
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>

using namespace std;

const int N = 3e4 + 1;
const int L = 14;

int v[N], aib[N], cf[N], n;

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

int caut(int val)
{
    if (val == 0)
    {
        return -1;
    }
    int r = 0, pas = 1 << L;
    while (pas != 0)
    {
        if (r + pas <= n && aib[r + pas] < val)///caut cel mai lung prefix cu suma < val
        {
            val -= aib[r + pas];
            r += pas;
        }
        pas >>= 1;
    }
    r++;///1+lungimea celui mai lung cu suma < val = cel mai scurt cu suma >= val
    return r;
}

int main()
{
    ifstream in("schi.in");
    ofstream out("schi.out");
    in >> n;
    ///suma obtinuta de aib pana la poz i = cate locuri libere au ramas pana la poz i
    for (int i = 1; i <= n; i++)
    {
        in >> v[i];
        actualizare(i, 1);///fiecare loc de la 1 la n e initial liber
    }
    in.close();
    for (int i = n; i >= 1; i--)
    {
        ///determin pozitia in clasamanetul final a celui care a concurat al i-lea
        int poz = caut(v[i]);///cel mai scurt prefix cu suma (locurilor libere) = v[i]
        actualizare(poz, -1);///am un loc liber mai putin pentru interogarile de la poz in sus
        cf[poz] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        out << cf[i] << "\n";
    }
    out.close();
    return 0;
}