Cod sursa(job #2019660)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 8 septembrie 2017 11:51:29
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#define ub(x) (x&(-x))
using namespace std;
ifstream f ("schi.in");
ofstream g ("schi.out");
int n,i,a[30002],aib[30002],j,b[30002],dr,st,poz,mij,mn;
int Sum (int poz)
{
    int S = 0;
    for (i=poz;i>0;i-=ub(i)) {
        S+=aib[i];
    }
    return S;
}
void scad (int poz)
{
    for (i=poz;i<=n;i+=ub(i)) {
        aib[i]--;
    }
}
int main()
{
    f>>n;
    for (j=1;j<=n;j++) {
        f>>a[j];
        aib[j]=ub(j);
    }
    for (j=n;j>=1;j--) {
        dr=n;
        st=1;
        mij=0;
        mn=n+1;
        while (st<=dr)
        {
            mij=(st+dr)/2;
            if (Sum(mij)==a[j] && mij<mn) {
                mn=mij;
                dr=mij-1;
            }
            else if (Sum(mij)>a[j]) {
                dr=mij-1;
            }
            else st=mij+1;
        }
        b[mn]=j;
        scad(mn);
    }
    for (j=1;j<=n;j++) {
        g<<b[j]<<" ";
    }
    return 0;
}