Submission #1514346


Source Code Expand

#include <bits/stdc++.h>

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
typedef std::vector<long> LI;
typedef std::queue<long> QI;
#define rep(i,n) for(long i = 0; i < (long)n; ++i)
const double pi = M_PI;
const long mod = 1000000007;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(long& x) { if( scanf("%ld", &x) < 0 ) exit(0); }
template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }
template<> void scan1(LI& xs) { for(long &x : xs) scan1(x); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   void dfs(LI &xs, long i, long total, LI &res) {
      if( i == (long)xs.size() ) {
         res.push_back(total);
         return;
      }
      dfs(xs, i + 1, total, res);
      dfs(xs, i + 1, total + xs[i], res);
   }
   std::vector<std::pair<long, long>> compress(LI &xs) {
      LI ys = xs;
      std::sort(ys.begin(), ys.end());
      std::vector<std::pair<long, long>> res;
      long n = ys.size();
      for(long i = 0; i < n; ++i) {
         if( i == 0 or ys[i-1] != ys[i] ) {
            res.push_back(std::make_pair(ys[i], 1));
         }
         else {
            res.back().second += 1;
         }
      }
      return res;
   }
   std::vector<std::pair<long, long>> gen(LI xs) {
      LI res;
      dfs(xs, 0, 0, res);
      return compress(res);
   }
   void solve() {
      long n, x; scan(n, x);
      LI xs(n); scan(xs);
      LI xsLow, xsHigh;
      for(long i = 0; i < n / 2; ++i) xsLow.push_back(xs[i]);
      for(long i = n / 2; i < n; ++i) xsHigh.push_back(xs[i]);
      auto ysLow = gen(xsLow);
      auto ysHigh = gen(xsHigh);
      std::reverse(ysHigh.begin(), ysHigh.end());
      long res = 0;
      {
         long i = 0, k = 0;
         while( i < (long)ysLow.size() and k < (long)ysHigh.size() ) {
            auto a = ysLow[i], b = ysHigh[k];
            if( a.first + b.first == x ) {
               res += a.second * b.second;
               i += 1, k += 1;
            }
            else if( a.first + b.first < x ) {
               i += 1;
            }
            else if( a.first + b.first > x ) {
               k += 1;
            }
            else assert(0);
         }
      }
      printf("%ld\n", res);
   }
};

int main() {
   loop std::unique_ptr<Solver>(new Solver())->solve();
}

Submission Info

Submission Time
Task C - 無駄なものが嫌いな人
User spica314
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3266 Byte
Status AC
Exec Time 12 ms
Memory 3820 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 28
Set Name Test Cases
All max_1.txt, max_2.txt, max_3.txt, max_4.txt, pair_1.txt, pair_2.txt, power2_1.txt, power2_2.txt, power2_3.txt, power2_4.txt, power2_5.txt, random_1.txt, random_2.txt, random_3.txt, random_4.txt, random_5.txt, random_6.txt, random_7.txt, random_8.txt, random_9.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt
Case Name Status Exec Time Memory
max_1.txt AC 6 ms 1776 KB
max_2.txt AC 8 ms 1776 KB
max_3.txt AC 6 ms 1776 KB
max_4.txt AC 8 ms 1776 KB
pair_1.txt AC 12 ms 2544 KB
pair_2.txt AC 8 ms 1776 KB
power2_1.txt AC 10 ms 2288 KB
power2_2.txt AC 8 ms 1776 KB
power2_3.txt AC 7 ms 1776 KB
power2_4.txt AC 7 ms 1776 KB
power2_5.txt AC 2 ms 640 KB
random_1.txt AC 10 ms 2924 KB
random_2.txt AC 10 ms 2924 KB
random_3.txt AC 12 ms 3820 KB
random_4.txt AC 12 ms 3820 KB
random_5.txt AC 8 ms 1776 KB
random_6.txt AC 6 ms 1428 KB
random_7.txt AC 9 ms 1776 KB
random_8.txt AC 11 ms 2416 KB
random_9.txt AC 9 ms 2924 KB
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 1 ms 256 KB
sample_4.txt AC 1 ms 256 KB
small_1.txt AC 1 ms 256 KB
small_2.txt AC 1 ms 256 KB
small_3.txt AC 1 ms 256 KB
small_4.txt AC 1 ms 256 KB