Cod sursa(job #1792188)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 30 octombrie 2016 10:37:04
Problema Interclasari Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include <cctype>
#define MAXBUF 1<<17
FILE*fi,*fout;
char buf[MAXBUF];
int pos=MAXBUF;
inline char nextch(){
    if(pos==MAXBUF){
        fread(buf,1,MAXBUF,fi);
        pos=0;
    }
    return buf[pos++];
}
inline int getnr(){
   char a=nextch();
   while(isdigit(a)==0)
      a=nextch();
   int nr=0;
   while(isdigit(a)==1){
      nr=nr*10+a-'0';
      a=nextch();
   }
   return nr;
}
#define MAXN 2000000
int v[MAXN+1];
inline int father(int nod){
    return nod/2;
}
inline int lson(int nod){
   return 2*nod;
}
inline int rson(int nod){
   return 2*nod+1;
}
inline void myswap(int x,int y){
   int aux=v[x];
   v[x]=v[y];
   v[y]=aux;
}
inline void urcare(int nod){
   while(father(nod)>0&&v[father(nod)]>v[nod]){
      myswap(nod,father(nod));
      nod=father(nod);
   }
}
inline void coborare(int nod,int n){
   int flag=1,aux;
   while(flag==1){
       aux=nod;
       if(lson(nod)<=n&&v[aux]>v[lson(nod)])
         aux=lson(nod);
       if(rson(nod)<=n&&v[aux]>v[rson(nod)])
         aux=rson(nod);
       if(nod==aux)
         flag=0;
       myswap(nod,aux);
       nod=aux;
   }
}
int main(){
   int n,k,p;
   fi=fopen("interclasari.in" ,"r");
   fout=fopen("interclasari.out" ,"w");
   k=getnr();
   n=0;
   while(k>0){
      k--;
      p=getnr();
      while(p>0){
         n++;
         v[n]=getnr();
         urcare(n);
         p--;
      }
   }
   fprintf(fout,"%d\n" ,n);
   while(n>0){
      fprintf(fout,"%d " ,v[1]);
      myswap(1,n);
      n--;
      coborare(1,n);
   }
   fclose(fi);
   fclose(fout);
   return 0;
}