Cod sursa(job #3296095)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 11 mai 2025 13:00:06
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3,Ofast,unroll-loops")
using namespace std;

const int NMAX = 1000001;
int v[NMAX], raspuns[NMAX];
int n;
int aint[4 * NMAX];

void update_recursiv(int nod, int stanga, int dreapta, int poz, int val)
{
    if (stanga == dreapta)
    {
        aint[nod] = val;
        return;
    }
    int mij = (stanga + dreapta) / 2;
    if (poz <= mij)
        update_recursiv(2 * nod, stanga, mij, poz, val);
    else
        update_recursiv(2 * nod + 1, mij + 1, dreapta, poz, val);
    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

void update(int poz, int val)
{
    update_recursiv(1, 1, n, poz, val);
}

int query_recursiv(int nod, int stanga, int dreapta, int query_x, int query_y)
{
    if (query_x > query_y)
        return 0;

    if (stanga == query_x && dreapta == query_y)
        return aint[nod];

    int mij = (stanga + dreapta) / 2;
    if (query_y <= mij)
        return query_recursiv(2 * nod, stanga, mij, query_x, query_y);
    if (query_x > mij)
        return query_recursiv(2 * nod + 1, mij + 1, dreapta, query_x, query_y);
    return query_recursiv(2 * nod, stanga, mij, query_x, mij) + query_recursiv(2 * nod + 1, mij + 1, dreapta, mij + 1, query_y);
}

int query(int query_x, int query_y)
{
    return query_recursiv(1, 1, n, query_x, query_y);
}

int cautbinar(int p)
{
    int st = 1, dr = n, sol = -1;

    while (st <= dr)
    {
        int m = (st + dr) / 2;
        int locuri_libere = query(1, m);

        if (locuri_libere >= p)
        {
            sol = m;
            dr = m - 1;
        }
        else
        {
            st = m + 1;
        }
    }

    return sol;
}

int main()
{
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        update(i, 1);

    for (int i = 1; i <= n; i++)
        scanf("%d", &v[i]);

    for (int i = n; i >= 1; i--)
    {
        int poz = cautbinar(v[i]);
        update(poz, 0);
        raspuns[poz] = i;
    }

    for (int i = 1; i <= n; i++)
        printf("%d\n", raspuns[i]);

    return 0;
}