Cod sursa(job #2591984)

Utilizator anabatAna Batrineanu anabat Data 31 martie 2020 20:06:47
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#include <algorithm>

#define NMAX 30000

int v[NMAX+1],aint[NMAX*4+1],v2[NMAX+1];

void update(int nod,int st,int dr,int poz,int val){
  if(st==dr){
    aint[nod]=val;
  }
  else{
    int mij=(st+dr)/2;
    if(poz<=mij){ ///stg
      update(2*nod,st,mij,poz,val);
    }
    else if(poz>mij){
      update(2*nod+1,mij+1,dr,poz,val);
    }
    aint[nod]=aint[2*nod]+aint[2*nod+1]; ///cate 0 uri avem pt un interval
  }
}

int query(int nod,int st,int dr,int poz){ ///afisam al poz-lea 0
  if(st==dr){
    return st;
  }
  else{
    int mij=(st+dr)/2;
    if(poz<=aint[2*nod]){
      return query(2*nod,st,mij,poz);
    }
    else if(poz>aint[2*nod]){
      return query(2*nod+1,mij+1,dr,poz-aint[2*nod]);
    }
  }
}

int main()
{
  FILE *fin,*fout;
  fin=fopen("schi.in","r");
  fout=fopen("schi.out","w");

  int n,i,pozint;
  fscanf(fin,"%d",&n);
  for(i=1;i<=n;i++){
    fscanf(fin,"%d",&v[i]);
    update(1,1,n,i,1);
  }
  for(i=n;i>=1;i--){
    pozint=query(1,1,n,v[i]);///poz in clasamentul final
    update(1,1,n,pozint,0); ///stergem nr
    v2[pozint]=i;
  }
  for(i=1;i<=n;i++){
    fprintf(fout,"%d\n",v2[i]);
  }

  fclose(fin);
  fclose(fout);
  return 0;
}