Cod sursa(job #2953998)

Utilizator Giulian617Buzatu Giulian Giulian617 Data 12 decembrie 2022 22:24:48
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
const int NMAX=30005;
int n,pos,SumTree[4*NMAX];
vector<int>v,ans;
void update(int node,int left,int right)
{
    if(left==right)///leaf
    {
        SumTree[node]=1;
        return;
    }
    int middle=(left+right)/2;
    if(pos<=middle)
        update(2*node,left,middle);///update left son
    else
        update(2*node+1,middle+1,right);///update right son
    SumTree[node]=SumTree[2*node]+SumTree[2*node+1];
}
int find_kth_zero(int k,int node,int left,int right)
{
    if(left==right)///leaf
        return left;///the answer
    int middle=(left+right)/2,left_side_zeroes=(middle-left+1)-SumTree[2*node];///because SumTree represents the number of ones
    if(k<=left_side_zeroes)
        return find_kth_zero(k,2*node,left,middle);///left son
    else
        return find_kth_zero(k-left_side_zeroes,2*node+1,middle+1,right);///right son, we deduce the zeroes from the left son
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    f>>n;
    v.resize(n+1);
    ans.resize(n+1);
    for(int i=1; i<=n; i++)
        f>>v[i];
    for(int i=n; i>=1; i--)///we take the positions in reverse order
    {
        pos=find_kth_zero(v[i],1,1,n);
        update(1,1,n);
        ans[pos]=i;
    }
    for(int i=1; i<=n; i++)
        g<<ans[i]<<'\n';
    return 0;
}