fork download
copy 
  1. //havel hakimi algorithm
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. int main(){
  7.  int t,n,i,temp,neg,k,zc,m=INT_MIN;
  8.  long long sum;
  9.  
  10.  scanf("%d",&t);
  11.  while(t--){
  12.    scanf("%d",&n);
  13.    zc=0;
  14.    sum=0;
  15.    vector<int>d;
  16.    for(i=0;i<n;i++){
  17.       scanf("%d",&temp);
  18.       d.push_back(temp);
  19.       sum+=temp;
  20.       if(temp>m)m=temp;
  21.       if(!temp)zc++;
  22.     }
  23.     if(n==0)printf("HAPPY\n");
  24.     else if(m>n)printf("SAD\n");
  25.     else if(sum%2){
  26.         printf("SAD\n");
  27.     }
  28.     else{
  29.        while(1){
  30.            // printf("looping %d\n",d.size());
  31.           if(zc==d.size()){
  32.                // printf("zeros\n");
  33.                 break;
  34.           }
  35.             neg=0;
  36.             zc=0;
  37.          sort(d.rbegin(),d.rend());
  38.          k=d[0];
  39.          d.erase(d.begin());
  40.          for(i=0;i<k;i++){
  41.            //  printf("d now %d at %d k=%d\n",d[i],i,k);
  42.              d[i]--;
  43.             if(d[i]<0){
  44.                neg++;
  45.              //  printf("found neg\n");
  46.                break;
  47.             }
  48.             if(!d[i]){zc++;}
  49.          }
  50.         if(neg>0)break;
  51.        }
  52.  
  53.        if(zc==d.size())printf("HAPPY\n");
  54.        else if(neg>0)printf("SAD\n");
  55.  
  56.     }
  57.  }
  58.  
  59. return 0;
  60. }
  61.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
8 8 7 6 6 5 3 2 2 2 1
stdout
copy 
SAD
SAD
SAD
SAD
SAD
SAD
SAD
SAD
https://ideone.com/pBEO3z
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!