Submission #857232


Source Code Expand

Copy
#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 fact(int n) {
    if (n > 0) {
        return n * fact(n - 1);
    } else {
        return 1;
    }
}

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++;	
	}
}
C=fact(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

Submission Time
Task C - Tak and Cards
User grayf
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3476 Byte
Status WA
Exec Time 2127 ms
Memory 179164 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 100
Status
AC × 2
WA × 1
TLE × 1
AC × 4
WA × 8
AC × 4
WA × 8
TLE × 12
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt, example_04.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
All example_01.txt, example_02.txt, example_03.txt, example_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt
Case Name Status Exec Time Memory
example_01.txt AC 4 ms 256 KB
example_02.txt WA 4 ms 256 KB
example_03.txt AC 4 ms 256 KB
example_04.txt TLE 2105 ms 256 KB
subtask1_01.txt AC 5 ms 256 KB
subtask1_02.txt WA 9 ms 256 KB
subtask1_03.txt WA 9 ms 256 KB
subtask1_04.txt WA 8 ms 256 KB
subtask1_05.txt WA 4 ms 256 KB
subtask1_06.txt AC 4 ms 256 KB
subtask1_07.txt WA 4 ms 256 KB
subtask1_08.txt WA 5 ms 256 KB
subtask1_09.txt WA 5 ms 256 KB
subtask2_01.txt TLE 2127 ms 179164 KB
subtask2_02.txt TLE 2105 ms 256 KB
subtask2_03.txt TLE 2122 ms 131424 KB
subtask2_04.txt TLE 2105 ms 256 KB
subtask2_05.txt TLE 2105 ms 256 KB
subtask2_06.txt TLE 2101 ms 256 KB
subtask2_07.txt TLE 2126 ms 178652 KB
subtask2_08.txt TLE 2105 ms 256 KB
subtask2_09.txt TLE 2105 ms 256 KB
subtask2_10.txt TLE 2105 ms 256 KB
subtask2_11.txt TLE 2102 ms 8560 KB