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 |
|
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 |