Cod sursa(job #287067)

Utilizator FlorianFlorian Marcu Florian Data 24 martie 2009 15:39:23
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<stdio.h>
#define Nmax 100002
int H[Nmax];
int n, sol[30002]; // sol[i] = concurentul care se afla pe pozitia i
int a[30002];
char viz[Nmax];
void read()
 {
  freopen("schi.in","r",stdin);
  freopen("schi.out","w",stdout);
  scanf("%d\n",&n);
  int i;
  for(i=1;i<=n;++i)
   scanf("%d",&a[i]);
 }
void update(int n, int l, int r, int p)
 {
  if(l>=r)
   {
    viz[n] = '1';
    H[n] = 1;
    return;
   }
  int m=(l+r)/2, fs=2*n, fd=2*n+1;
  if(p<=m) update(fs,l,m,p);
  else update(fd,m+1,r,p);

  H[n] = H[fs] + H[fd];

  if(H[n]) viz[n] = '1';
 }
int s, P;
void elimin(int n, int l, int r, int x)
 {
  if(l>=r)
   {
     P = r;
     H[n] = 0; viz[n] = '0';
     return;
   }
  int m=(l+r)/2, fs=2*n, fd=2*n+1;
  if(viz[fs]=='1' && viz[fd]=='1')
   {
     if(s + H[fs] < x)
      {
       s+=H[fs];
       elimin(fd, m+1, r, x);
      }
     else elimin(fs,l,m,x);
   }
  else if(viz[fs]=='0' && viz[fd]=='1') elimin(fd,m+1,r,x);
  else if(viz[fs]=='1') elimin(fs,l,m,x);
  else viz[n] = '0';

  H[n] = H[fs] + H[fd];
  if(!H[n]) viz[n] = '0';
 }
int main()
 {
  read();
  int i;
  for(i=n;i>=1;--i) update(1,1,n,i);
  for(i=n;i>=1;--i)
   {
    s=0;
    elimin(1,1,n,a[i]);
    sol[P] = i;
   }
  for(i=1;i<=n;++i) printf("%d\n",sol[i]);
  return 0;
 }