Cod sursa(job #1778957)

Utilizator bogdi1bogdan bancuta bogdi1 Data 14 octombrie 2016 15:55:19
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>

using namespace std;
int aib[30005],n;
int v[30005];
int f[30005];
void update(int poz,int val)
{
  for( ; poz<=n; poz+=poz&-poz)
    aib[poz]+=val;
}
int query(int poz)
{
  int s=0;
  for( ; poz>0; poz-=poz&-poz)
    s=s+aib[poz];
  return s;
}
int bs(int val)
{
    int st=1,dr=n,med,last=30005,nr;
    while(st<=dr){
        med=(st+dr)/2;
        nr=query(med);
        if(nr==val && last>med)
            last=med;
        else{
            if(nr<val)
                st=med+1;
            else
                dr=med-1;
        }
    }
    return last;
}
int main()
{   freopen("schi.in", "r",stdin);
    freopen("schi.out", "w",stdout);
    int i,nr;
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d", &v[i]);
        aib[i]=i&-i;
    }
    for(i=n; i>0; i--){
        nr=bs(v[i]);
        f[nr]=i;
        update(nr, -1);
    }
    for(i=1; i<=n; i++)
        printf("%d\n", f[i]);
    return 0;
}