Cod sursa(job #1807681)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 16 noiembrie 2016 20:30:57
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>

using namespace std;
int n,p,i,j,k,s,w[30005],q[30005],v[16][30005];
void adauga(int poz)
{
    j=0;
    while(j<=k)
    {
        v[j][poz]--;
        j++;
        poz=(poz+1)/2;
    }
}
int cauta(int poz)
{
    j=k;
    p=1;
    while(j)
    {
        if(v[j-1][2*p-1]>=poz) p=2*p-1;
        else
        {
            p=2*p;
            poz-=v[j-1][p-1];
        }
        j--;
    }
    adauga(p);
    return p;
}
int main()
{
    ifstream f("schi.in");
    ofstream g("schi.out");
    f>>n;
    p=n;
    k=0;
    s=1;
    while(p>1)
    {
        for(i=1; i<=p; i++)
        {
            v[k][i]=s;
        }
        s*=2;
        k++;
        p=(p+1)/2;
    }
    v[k][1]=s;
    for(i=1; i<=n; i++)
        f>>w[i];
    for(i=n; i>=1; i--)
    {
        w[i]=cauta(w[i]);
        q[w[i]]=i;
    }
    for(i=1; i<=n; i++)
        g<<q[i]<<'\n';
    f.close(); g.close();
    return 0;
}