Cod sursa(job #2156641)

Utilizator DavidLDavid Lauran DavidL Data 8 martie 2018 21:30:03
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#define MAX 30005
using namespace std;
ifstream fi("schi.in");
ofstream fo("schi.out");

int n,x[MAX],rez[MAX];
int A[MAX];

int sum(int poz)
{
    int rez=0;
    while (poz)
    {
        rez+=A[poz];
        poz-=((poz^(poz-1))&poz);
    }
    return rez;
}

void update(int val,int poz)
{
    while (poz<=n)
    {
        A[poz]+=val;
        poz+=((poz^(poz-1))&poz);
    }
}

int cautare(int x)
{
     int st=1,dr=n,m,val;
     while(st<=dr){
        m=(st+dr)/2;
        int aux=sum(m);
        if(aux==x){
            dr=m-1;
            val=m;
        }
        else if(aux<x){
            st=m+1;
        }
        else dr=m-1;
    }
    return val;
}

int main()
{
    fi>>n;
    for (int i=1; i<=n; i++)
        fi>>x[i],update(1,i);


    for (int i=n; i>=1; i--)
    {
        int poz=cautare(x[i]);
        rez[poz]=i;
        //fo<<i<<" se afla pe "<<poz<<"\n";
        update(-1,poz);
    }
    for (int i=1; i<=n; i++)
        fo<<rez[i]<<"\n";
    return 0;
}