Cod sursa(job #3318342)

Utilizator teobsnTeodor Bostan teobsn Data 28 octombrie 2025 04:09:12
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
using namespace std;

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

int ai[400005];
int v[100005];
int rez[100005];


void build(int node, int st, int dr)
{
    if (st == dr)
        ai[node] = 1;
    else
    {
        int mid = (st + dr) / 2;
        build(2 * node, st, mid);
        build(2 * node + 1, mid + 1, dr);
        ai[node] = ai[2 * node] + ai[2 * node + 1];
    }
}

void update(int node, int st, int dr, int pos)
{
    if (st == dr)
        ai[node] = 0;
    else
    {
        int mid = (st + dr) / 2;

        if (pos <= mid)
            update(2 * node, st, mid, pos);
        else
            update(2 * node + 1, mid + 1, dr, pos);

        ai[node] = ai[2 * node] + ai[2 * node + 1];
    }
}

int search(int node, int st, int dr, int s)
{
    if (ai[node] == s && !rez[dr]) // Exista oare o solutie mai eleganta decat acest !rez[dr]?
        return dr;
    else
    {
        int mid = (st + dr) / 2;

        if (s <= ai[2 * node])
            return search(2 * node, st, mid, s);
        else
            return search(2 * node + 1, mid + 1, dr, s - ai[2 * node]);
    }
}

int main()
{
    int n;
    fin >> n;

    for (int i = 0; i < n; i++)
        fin >> v[i];

    build(1, 0, n - 1);

    for (int i = n - 1; i >= 0; i--)
    {
        int pos = search(1, 0, n - 1, v[i]);
        
        rez[pos] = i + 1; // convert to 1-based index
        update(1, 0, n - 1, pos);
    }

    for (int i = 0; i < n; i++)
        fout << rez[i] << "\n";

    return 0;
}