Cod sursa(job #2898457)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 6 mai 2022 19:49:51
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>
#define NMAX 30005

using namespace std;

/*******************************/
// INPUT / OUTPUT
ifstream f("schi.in");
ofstream g("schi.out");
/*******************************/
/// GLOBAL DECLARATIONS

int N;
int pos[NMAX], ans[NMAX];
int arb[4 * NMAX];
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    f >> N;          
}
///-------------------------------------
void Update(const int &st, const int &dr, const int &idx, const int &pos, const int &val)
{
    if (st == dr)
    {
        arb[idx] = val;
        return;
    }

    int mid = (st + dr) / 2;

    if (pos <= mid) Update(st, mid, 2 * idx, pos, val);
    else Update(mid + 1, dr, 2 * idx + 1, pos, val);
    arb[idx] = arb[2 * idx] + arb[2 * idx + 1];
}
///-------------------------------------
int Query(const int &st, const int &dr, const int &idx, const int &val)
{
    if (st == dr)
    {
        return st;
    }

    int mid = (st + dr) / 2;
    if (arb[2 * idx] >= val)
    {
        return Query(st, mid, 2 * idx, val);
    }
    return Query(mid + 1, dr, 2 * idx + 1, val - arb[2 * idx]);
}
///-------------------------------------
inline void Solution()
{
    for (int i = 1 ; i <= N ; ++ i)
    {
        f >> pos[i];
        Update(1, N, 1, i, 1);
    }

    int finalPos;
    for (int i = N ; i >= 1 ; -- i)
    {
        finalPos = Query(1, N, 1, pos[i]);
        ans[finalPos] = i;
        Update(1, N, 1, finalPos, 0);
    }
}
///-------------------------------------
inline void Output()
{
    for (int i = 1 ; i <= N ; ++ i)
    {
        g << ans[i] << "\n";
    }
}
///-------------------------------------
int main()
{
    ReadInput();
    Solution();
    Output();
    return 0;
}