Contest Duration: - (local time) (100 minutes) Back to Home

Submission #857149

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.0005);
else {
down.push_back(x[i]+i*0.0005);
}
}
//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 2016-08-28 22:38:36+0900 C - Tak and Cards grayf C++14 (GCC 5.4.1) 0 3478 Byte WA 2126 ms 231772 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
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 4 ms 256 KB
subtask1_02.txt WA 9 ms 256 KB
subtask1_03.txt WA 8 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 4 ms 256 KB
subtask1_09.txt WA 4 ms 256 KB
subtask2_01.txt TLE 2126 ms 223836 KB
subtask2_02.txt TLE 2101 ms 256 KB
subtask2_03.txt TLE 2114 ms 131424 KB
subtask2_04.txt TLE 2101 ms 256 KB
subtask2_05.txt TLE 2101 ms 256 KB
subtask2_06.txt TLE 2101 ms 256 KB
subtask2_07.txt TLE 2123 ms 231772 KB
subtask2_08.txt TLE 2104 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