Cod sursa(job #3134437)

Utilizator AnacrmCaraiman Ana Anacrm Data 29 mai 2023 00:28:44
Problema Schi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<bits/stdc++.h>
using namespace std;
ifstream r("schi.in");
ofstream wr("schi.out");

int v[60000],sol[60000],w[60000] ,i,n,sum;

void creare(int p ,int st ,int dr ,int x ,int val)
{
    if ( st == dr )
    {
        v[p] = val;
        return;
    }else
    {
        int mij = (st + dr)/2;
        if ( x <= mij )
            creare(2 * p , st , mij , x , val);
        else
            creare(2*p + 1 , mij + 1 , dr , x , val );

        v[p] = v[ 2*p ] + v[ 2*p+1 ];
    }
}
void query(int pos, int st, int dr, int a, int b){
    if(st>b or dr<a) return;
    if(a<=st and dr<=b){
        sum+=v[pos];
        return;
    }

    query(2*pos, st, (st+dr)/2, a, b);
    query(2*pos+1, (st+dr)/2+1, dr, a, b);
}


int main()
{ int in,s,mij;

    r>>n;

    for(i=1;i<=n;i++) r>>w[i];
    for(i=n;i>=1;i--){
        in=1, s=n;
        mij=(in+s)>>1;
        while(in<s){
            sum=0;
            query(1,1,n,1,mij);
            if(mij<sum+w[i]) in=mij+1;
            else s=mij;
            mij=(in+s)>>1;
        }

        creare(1,1,n,mij,1);
        sol[mij]=i;
    }
    for(i=1;i<=n;i++)
        wr<<sol[i]<<endl;

    return 0;
}