Cod sursa(job #2606163)

Utilizator anabatAna Batrineanu anabat Data 27 aprilie 2020 11:01:48
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <stdio.h>

#define NMAX 30000

int aint[NMAX*4+1]; ///cati de 1 (neeliminate) am pt un interval din aint

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){
      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]; ///cati de 1 avem pt un interval
  }
}

int query(int nod,int st,int dr,int left,int right){ ///afiseaza nr de 1 uri
  if(st==left&&dr==right){
    return aint[nod];
  }
  else{
    int mij=(st+dr)/2;
    if(right<=mij){
      return query(2*nod,st,mij,left,right);
    }
    else if(left>mij){
      return query(2*nod+1,mij+1,dr,left,right);
    }
    else{
      return query(2*nod,st,mij,left,mij)+query(2*nod+1,mij+1,dr,mij+1,right);
    }
  }
}

int query2(int nod,int st,int dr,int poz){ ///afisez al catelea nr neeliminat (1) este
  if(st==dr){
    return st;
  }
  else{
    int mij=(st+dr)/2;
    if(poz<=aint[2*nod]){ ///stg
      return query2(2*nod,st,mij,poz);
    }
    else if(poz>aint[2*nod]){ ///dr
      return query2(2*nod+1,mij+1,dr,poz-aint[2*nod]);
    }
  }
}

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

  int n,i,elimcif,poz,x,PAS;
  fscanf(fin,"%d",&n);
  for(i=1;i<=n;i++)
    update(1,1,n,i,1);

  PAS=1;
  elimcif=1;
  poz=0;

  for(i=1;i<=n;i++){
    poz=query(1,1,n,elimcif,n); ///nr de nr neeliminate
    if(poz<PAS){
      PAS=PAS-poz;
      elimcif=query2(1,1,n,PAS); ///ne gaseste al catelea PAS-poz-lea este 1 in stg
      update(1,1,n,elimcif,0); ///elimin
    }
    else{ ///mergem doar in dr
      elimcif+=PAS;
      update(1,1,n,elimcif,0); ///elimin
    }
    fprintf(fout,"%d ", elimcif);
    PAS++;
  }
  fclose(fin);
  fclose(fout);

  return 0;
}