Cod sursa(job #2606201)

Utilizator anabatAna Batrineanu anabat Data 27 aprilie 2020 12:04:30
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.22 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,PAS,nrelimsir,to; ///to= al catelea 1 il caut
  fscanf(fin,"%d",&n);
  for(i=1;i<=n;i++)
    update(1,1,n,i,1);

  PAS=1;
  elimcif=1;
  poz=0;
  nrelimsir=n; ///nr de numere neeliminate DIN TOT SIRUL

  for(i=1;i<=n;i++){
    poz=query(1,1,n,elimcif,n); ///nr de nr neeliminate
    to=(PAS%nrelimsir);
    if(to==0)
      to=nrelimsir;
    if(poz<to){ ///dr+stg
      to-=poz ;
      elimcif=query2(1,1,n,to); ///ne gaseste al catelea PAS-poz-lea este 1 in stg
      update(1,1,n,elimcif,0); ///elimin
    }
    else{ ///mergem doar in dr
      ///in query2 caut ce e in tot sirul asa ca nu vreau al PAS ulea din tot sirul vrei al PAS + queryasta din tot sirul
      elimcif=query2(1,1,n,to+query(1,1,n,1,elimcif));
      update(1,1,n,elimcif,0); ///elimin
    }
    fprintf(fout,"%d ",elimcif);
    PAS++;
    nrelimsir--;
  }

  fclose(fin);
  fclose(fout);

  return 0;
}