Cod sursa(job #3140697)

Utilizator Samoila_AlexandruSamoilaAlexandru Samoila_Alexandru Data 8 iulie 2023 21:09:20
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <iostream>

using namespace std;

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

const int nMax=3e4+5;

int n, v[nMax], aib[nMax], p[nMax];

void update(int p, int val)
{
    for(int i=p; i<=n; i+=(i&-i))
        aib[i]+=val;
}

int query(int p)
{
    int s=0;
    for(int i=p; i; i-=(i&-i))
        s+=aib[i];
    return s;
}

int cb(int x)
{
    int st=1, dr=n, poz=0;

    while(st<=dr)
    {
        int m=(st+dr)>>1;
        int sm=query(m);

        if(sm==x)
            poz=m, dr=m-1;
        else if(sm < x)
            st=m+1;
        else dr=m-1;
    }

    return poz;
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);

    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i];
        update(i, 1);
    }

    for(int i=n; i>=1; i--)
    {
        int poz=cb(v[i]);
        p[poz]=i;
        update(poz, -1);
    }

    for(int i=1; i<=n; i++)
        fout<<p[i]<<'\n';

    fin.close();
    fout.close();

    return 0;
}