Submission #856868

---

Source Code Expand

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<numeric>
#include<math.h>
#include<vector>

using namespace std;
template < class BidirectionalIterator >
bool next_combination ( BidirectionalIterator first1 ,
  BidirectionalIterator last1 ,
  BidirectionalIterator first2 ,
  BidirectionalIterator last2 )
{
  if (( first1 == last1 ) || ( first2 == last2 )) {
    return false ;
  }
  BidirectionalIterator m1 = last1 ;
  BidirectionalIterator m2 = last2 ; --m2;
  while (--m1 != first1 && !(* m1 < *m2 )){
  }
  bool result = (m1 == first1 ) && !(* first1 < *m2 );
  if (! result ) {
    // ①
    while ( first2 != m2 && !(* m1 < * first2 )) {
      ++ first2 ;
    }
    first1 = m1;
    std :: iter_swap (first1 , first2 );
    ++ first1 ;
    ++ first2 ;
  }
  if (( first1 != last1 ) && ( first2 != last2 )) {
    // ②
    m1 = last1 ; m2 = first2 ;
    while (( m1 != first1 ) && (m2 != last2 )) {
      std :: iter_swap (--m1 , m2 );
      ++ m2;
    }
    // ③
    std :: reverse (first1 , m1 );
    std :: reverse (first1 , last1 );
    std :: reverse (m2 , last2 );
    std :: reverse (first2 , last2 );
  }
  return ! result ;
}
 
template < class BidirectionalIterator >
bool next_combination ( BidirectionalIterator first ,
  BidirectionalIterator middle ,
  BidirectionalIterator last )
{
  return next_combination (first , middle , middle , last );
}


int N;
int A;
vector<int> x;
int C = 0;
vector<double> up;
vector<double> down;
int kari;
vector<long long int> sum;
long long int sumk;

int main(){
cin>>N;
cin>>A;
for(int i=0;i<N;i++){	
cin>>kari;
	x.push_back(kari);	
	x[i]-=A;
	if(x[i]==0)C++;
}
sort(x.begin(),x.end());
for(int i=0;i<N;i++){
	if(x[i]>0)up.push_back(x[i]+i*0.0001);
	else {
		down.push_back(x[i]+i*0.0001);
	}
}
//printf("%d,%d\n\n",up.size(),down.size());

if(up.size()>down.size()){
	for(int r=1;r<=down.size();r++){
		do{
			sumk=0;
  				for(int i=0;i<r;i++){
				  sumk+=floor(down[i]);
				 }
				//  printf("a%Lf,%d ",sumk,r);
			   if(sumk!=0) sum.push_back(sumk);//すべての組み合わせを入れる。
  		}while(next_combination(down.begin(),down.begin()+r,down.end()));
	}
	for(int r=1;r<=up.size();r++){
		do{
			sumk=0;
  				for(int i=0;i<r;i++){
				  sumk+=floor(up[i]);
				 }
				//  printf("b%Lf",sumk);
			   for(int i=0;i<sum.size();i++){
			//    printf("\n%Lfと%Lf",sum[i],sumk);
			   		if(sum[i]+sumk==0.0){C++;}
			   }
  		}while(next_combination(up.begin(),up.begin()+r,up.end()));
	}
}
else {
		for(int r=1;r<=up.size();r++){
		 do{
			sumk=0;
  				for(int i=0;i<r;i++){
				  sumk+=floor(up[i]);
				 }
		//		 printf("a%Lf,%d ",sumk,r);
			if(sumk!=0)  sum.push_back(sumk);//すべての組み合わせを入れる。
  		 }while(next_combination(up.begin(),up.begin()+r,up.end()));
		}
		
		for(int r=1;r<=down.size();r++){
		 do{
			sumk=0;
  				for(int i=0;i<r;i++){
				  sumk+=floor(down[i]);
				 }
			//	  printf("b%Lf",sumk);
			   for(int i=0;i<sum.size();i++){
			//   printf("\n%Lfと%Lf",sum[i],sumk);
			   		if(sum[i]+sumk==0.0){C++;}
			   }
  			}while(next_combination(down.begin(),down.begin()+r,down.end()));
		}
}





printf("%d\n",C);

return 0;
}

Submission Info

Judge Result