Cod sursa(job #1508705)

Utilizator Iustin48Ventaniuc Iustin Iustin48 Data 22 octombrie 2015 21:16:52
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#define zero(poz) ((poz^(poz-1))&poz)
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n,log,poz,aib[30001],sol[30001],v[30001],x;
int query(int poz)
{
    int s=0;
    for(;poz;poz-=zero(poz))
        s+=aib[poz];
    return s;
}
int main()
{
    f>>n;
    for(log=2;log<=n;log<<1);
    for(int i=1;i<=n;++i)
    {
        f>>v[i];
        poz=i;
        for(;poz<=n;poz+=zero(poz))
            ++aib[poz];
    }
    for(int i=n;i;--i)
    {
        x=v[i];
        int lg=log;
        for(poz=0;lg;lg>>1)
            if(poz+lg<=n&&query(poz+lg)<=x)
                poz+=lg;
        sol[poz]=i;
        for(;poz<=n;poz+=zero(poz))
            --aib[poz];
    }
    for(int i=1;i<=n;++i)
        g<<sol[i]<<" ";
    g.close();
    return 0;
}