Cod sursa(job #2099065)

Utilizator ScarymovieMocanu Alexandru Scarymovie Data 3 ianuarie 2018 22:00:30
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#define zeroes(x) (x^(x-1))&x
using namespace std;
int n,aib[30005],place[30005],table[30005],tag[30005];
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=zeroes(i))
        aib[i]+=val;
}
int cautbin(int val,int putere)
{
    int suma=0,sol=0,ans;
    for(int i=putere;i>=1;i/=2)
        {
            if(sol+i<=n)
                {
                    if(suma+aib[sol+i]<val) {suma+=aib[sol+i];sol+=i;}
                    if(suma+aib[sol+i]==val) ans=sol+i;
                }
        }
    return ans;
}
int main()
{
    ifstream f("schi.in");
    ofstream g("schi.out");
    f>>n;
    int putere=1;
    while(putere<=n) putere*=2;
    putere/=2;
    for(int i=1;i<=n;++i)
        {
            f>>place[i];
            update(i,1);
            tag[i]=1;
        }
    for(int i=n;i>=1;--i)
        {
            int poz=cautbin(place[i],putere);
            table[poz]=i;
            update(poz,-1);
        }
    for(int i=1;i<=n;++i) g<<table[i]<<'\n';
    return 0;
}