Cod sursa(job #3177774)

Utilizator Giulian617Buzatu Giulian Giulian617 Data 29 noiembrie 2023 23:01:53
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n,pos;
vector<int>v,ranking,aib;
void update(int node,int value)
{
    for(; node<=n; node+=node&(-node))
        aib[node]+=value;
}
int query(int node)
{
    int ans=0;
    for(; node>0; node-=node&(-node))
        ans+=aib[node];
    return ans;
}
int magical_binary_search(int value)
{
    int ans=0,curr_sum=0;
    for(int step=(1<<30); step>0; step>>=1) ///we search for the last position with the sum strictly smaller than value
        if(ans+step<=n && curr_sum+aib[ans+step]<value)
        {
            ans+=step;
            curr_sum+=aib[ans];
        }
    if(ans+1>n || query(ans+1)!=value) ///if the sum for the next position isn't equal to value we return -1
        return -1; ///not gonna happen in this problem
    return ans+1;

}
int main()
{
    f>>n;
    v.resize(n+1);
    ranking.resize(n+1);
    aib.resize(n+1);
    ///later we want to find the v[i] 1,
    ///so its easier to start with all elements being 1
    for(int i=1; i<=n; i++)
        update(i,1);
    for(int i=1; i<=n; i++)
        f>>v[i];
    for(int i=n; i>=1; i--)
    {
        pos=magical_binary_search(v[i]); ///returns the position of the v[i] 1
        update(pos,-1); /// we update that position with 0 because it can't be used anymore
        ranking[pos]=i;
    }
    for(int i=1; i<=n; i++)
        g<<ranking[i]<<'\n';
    return 0;
}