Cod sursa(job #3131368)

Utilizator NeganAlex Mihalcea Negan Data 19 mai 2023 22:29:22
Problema Schi Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 30005;
ifstream fin("schi.in");
ofstream fout("schi.out");

int n;
int a[NMAX];
int sol[NMAX];
int aint[NMAX];
int Leftson(int node)
{
    return 2 * node;
}
int Rightson(int node)
{
    return 2 * node + 1;
}
void Build(int node, int left, int right)
{
    if(left == right)
    {
        aint[node] = 1;
        return;
    }
    int mid = (left + right) / 2;
    Build(Leftson(node), left, mid);
    Build(Rightson(node), mid + 1, right);
    aint [node] = aint[Leftson(node)] + aint[Rightson(node)];
}
void Update(int node, int left, int right, int poz)
{
    if(left == right)
    {
        aint[node] = 0;
        return;
    }
    int mid = (left + right) / 2;
    if(poz <= mid)
        Update(Leftson(node), left, mid, poz);
    else
        Update(Rightson(node), mid + 1, right, poz);
    aint[node] = aint[Leftson(node)] + aint[Rightson(node)];
}
int Query(int node, int left, int right, int poz)
{
    if(left == right)
        return left;
    int mid = (left + right) / 2;
    if(poz <= aint[Leftson(node)])
        return Query(Leftson(node), left, mid, poz);
    else
        return Query(Rightson(node), mid + 1, right, poz - aint[Leftson(node)]);
}
int main()
{
    int i;
    fin >> n;
    for(i = 1;i <= n;i++)
        fin >> a[i];
    Build(1, 1, n);
    for(i = n;i >= 1;i--)
    {
        int k = Query(1, 1, n, a[i]);
        Update(1, 1, n, k);
        sol[k] = i;
    }
    for(i = 1;i <= n;i++)
        fout << sol[i] << "\n";
    return 0;
}