Cod sursa(job #736286)

Utilizator Smaug-Andrei C. Smaug- Data 18 aprilie 2012 12:47:12
Problema Schi Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <cstdio>

#define MAXN 30050

int T[MAXN], N;

int query(int x){
  
  int res=0;
  
  for( ; x; x-=(x^(x-1))&x)
    res+=T[x];
 
  return res;
  
}

void update(int x){
  
  for( ; x<=N; x+=(x^(x-1))&x)
    T[x]++;
  
}

int main(){
  
  freopen("schi.in", "r", stdin);
  freopen("schi.out", "w", stdout);
  
  int i, A[MAXN], aux, P[MAXN], pos;
  
  scanf("%d", &N);
  for(i=0; i<N; i++)
    scanf("%d", A+i);
  
  for(i=N-1; i>=0; i--){
    pos=0;
    aux=A[i]+query(A[i]);
    while(aux != pos){
      pos=aux;
      aux=A[i]+query(aux);
    }
    P[pos]=i;
    update(pos);
  }
  
  for(i=1; i<=N; i++)
    printf("%d\n", P[i]+1);
  
  return 0;
  
}