Cod sursa(job #2606169)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 27 aprilie 2020 11:24:59
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 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,sz, to;
  fscanf(fin,"%d",&n);
  for(i=1;i<=n;i++)
    update(1,1,n,i,1);

  PAS=1;
  elimcif=1;
  poz=0;
  sz = n ;
  for(i=1;i<=n;i++){
    poz=query(1,1,n,elimcif,n); ///nr de nr neeliminate
    to = (PAS%sz) ;
    if (to == 0 )
      to = sz ;
    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
      /// tu in query2 cauti ce e in tot sirul asa ca nu vrei 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++;
    sz--;
  }
  fclose(fin);
  fclose(fout);

  return 0;
}