Cod sursa(job #2108438)

Utilizator VoineaAndreiVoinea Ioan-Andrei VoineaAndrei Data 18 ianuarie 2018 12:28:49
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;

#define n_Max 30001

ifstream f("schi.in");
ofstream g("schi.out");

int n;
int v[n_Max];
int aib[n_Max];
int poz[n_Max];

void update(int x){
    //parcurgem din tata in tata
    for(int i=x;i<=n;i+=(i&-i))
        aib[i]--;
}

int query(int k){
    int r=0;
    //parcurgem din fiu in fiu
    for(int i=k;i>=1;i-=(i&-i))
        r+=aib[i];
    return r;
}

int bin_srch (int s,int d,int x)
{
    int k;
    while(s<=d){
        k=(s+d)/2;
        int nr=query(k);
        if(nr<x)
            s=k+1;
        else
            d=k-1;

    }

    update(d+1);
    return d+1;
}


int main()
{
    f>>n;
    for(int i=1;i<=n;++i)
        f>>v[i];


    for(int i=1;i<=n;++i)
        aib[i]=(i&-i);


    for(int i=n; i>=1; i--){
        int p = bin_srch(1, n, v[i]);
        poz[p]=i;
    }


    for(int i=1; i<=n; i++)
        g<<poz[i]<<'\n';




}