Cod sursa(job #2197426)

Utilizator tudorbuhniaTudor Buhnia tudorbuhnia Data 22 aprilie 2018 08:32:47
Problema Schi Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
using namespace std;
int v[70000],vc[30005],vr[30005],ls,ld;
void tree(int n)
{
    int x=1,cnt=1,f=1;
    while(f<n)
        f=f*2;
    ls=f;
    ld=ls*2-1;
    while(1)
    {
        for(int i=cnt;i<cnt+x;i++)
            v[i]=f;
        cnt+=x;
        if(x>=n)
            break;
        x=x*2;
        f=f/2;
    }
}
bool bt(int n)
{
    if(ls<=n && n<=ld)
        return 1;
    return 0;
}
int main()
{
    ifstream cin("schi.in");
    ofstream cout("schi.out");
    int n,x,cnt,c2;
    cin >> n;
    tree(n);
    for(int i=0;i<n;i++)
        cin >> vc[i];
    for(int i=n-1;i>=0;i--)
    {
        x=vc[i];
        cnt=1;
        while(bt(cnt)==0)
        {
            if(x<v[cnt])
            {
                cnt=cnt*2;
                continue;
            }
            c2=v[cnt];
            while(c2<x)
            {
                cnt++;
                c2+=v[cnt];
            }
            c2-=v[cnt];
            x-=c2;
            cnt=cnt*2;
        }
        c2=v[cnt];
        while(c2<x)
        {
            cnt++;
            c2+=v[cnt];
        }
        vr[cnt-ls]=i+1;
        while(cnt>0)
        {
            v[cnt]--;
            cnt=cnt/2;
        }
    }
    for(int i=0;i<n;i++)
        cout << vr[i] << endl;
    return 0;
}