Cod sursa(job #2824283)

Utilizator CelestinNegraru Celestin Celestin Data 31 decembrie 2021 23:29:27
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <fstream>
#define ub(x) ((x^(x-1))&x)
#define maxi 30000
using namespace std;
ifstream f;
ofstream g;
int v[maxi+10],aib[maxi+10],place[maxi+10],n;
void update(int poz,int val)
{
    for(int i=poz;i<=n;i+=ub(i))
        aib[i]+=val;
    return;
}
int sum(int poz)
{
    int suma=0;
    for(int i=poz;i>0;i-=ub(i))
        suma+=aib[i];
    return suma;
}
void read()
{
    f.open("schi.in",ios::in);
    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i];
    f.close();
    return;
}
int binary(int x)
{
    int st=1,dr=n,pozmin=100000;
    while(st<=dr)
    {
        int mid=(st+dr)>>1;
        int smid=sum(mid);
        if(smid==x&&mid<pozmin)
            pozmin=mid;
        else if(smid>=x)
             dr=mid-1;
            else st=mid+1;
    }
    return pozmin;
}
void clasament()
{
    g.open("schi.out",ios::in);
    read();
    for(int i=1;i<=n;i++)
        update(i,1);
    for(int i=n;i>=1;i-=1)
    {
        int x=binary(v[i]);
        place[x]=i;
        update(x,-1);
    }
    for(int i=1;i<=n;i++)
        g<<place[i]<<'\n';
}
int main()
{
    clasament();
    return 0;
}