Cod sursa(job #3248999)

Utilizator angelaAngela Visuian angela Data 14 octombrie 2024 12:18:05
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <cstdio>

#define NMax 30005

using namespace std;

int N, st[4 * NMax], ord[NMax], Q[NMax], NQ;

void Update(int x, int l, int r, int poz, int V)
{
    int m = (l + r) / 2;
    if (l == r)
    {
        st[x] = V;
        return;
    }
    
    if (poz <= m)
        Update(2 * x, l, m, poz, V);
    
    if (poz > m)
        Update(2 * x + 1, m + 1, r, poz, V);
    
    st[x] = st[2 * x] + st[2 * x + 1];
}

int Query (int x, int l, int r, int S)
{
    if (l == r)
        return l;
    
    int m = (l + r) / 2;
    
    if (st[2 * x] >= S)
        return Query(2 * x, l, m, S);
    
    return Query(2 * x + 1, m + 1, r, S - st[2 * x]);
}

void Read()
{
    freopen ("schi.in", "r", stdin);
    scanf ("%d", &N);
    for (NQ = 1; NQ <= N; ++NQ)
    {
        scanf("%d", &Q[NQ]);
        Update (1, 1, N, NQ, 1);
    }
    --NQ;
}

void PrintSol()
{
    freopen ("schi.out", "w", stdout);
    for (int i = 1; i <= N; ++i)
        printf ("%d\n", ord[i]);
}

int main()
{
    Read();
    for (; NQ; --NQ)
    {
        int loc_real = Query(1, 1, N, Q[NQ]);
        ord[loc_real] = NQ;
        Update(1, 1, N, loc_real, 0);
       
    }
    
    PrintSol();
    return 0;
}