Cod sursa(job #3245012)

Utilizator maryyMaria Ciutea maryy Data 26 septembrie 2024 23:35:18
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
const int nmax=3e4;
int v[nmax+1], aib[nmax+1], n, rez[nmax+1];
void update(int pos, int val)
{
    while(pos<=n)
    {
        aib[pos] += val;
        pos += (pos & -pos);
    }
}
int query(int pos)
{
    int rez=0;
    while(pos)
    {
        rez += aib[pos];
        pos -= (pos & -pos);
    }
    return rez;
}
int fen_bin_search(long long sum)
{
    int ans=0, curr_sum=0;
    for(int step=(1<<30); step>0; step=step/2)
        if(ans+step<=n && curr_sum+aib[ans+step]<sum)
        {
            ans += step;
            curr_sum += aib[ans];
        }
    if(ans+1>n || query(ans+1)!=sum)
        return -1;
    return ans+1;
}
int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
    {
        in>>v[i];
        update(i, 1);//pozitiile initial sunt toate 1->cand se ocupa una devine 0 pozitia respectiva
    }
    int pos;
    for(int i=n; i>=1; i--)
    {
        pos=fen_bin_search(v[i]);//pe ce pozitie reala ajunge(pozitie care trebuie sa aiba v[i] 1-uri in fata ei)
        rez[pos]=i;
        update(pos, -1);
    }
    for(int i=1; i<=n; i++)
    {
        out<<rez[i]<<'\n';
    }
}