#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <queue>
#include <unordered_map>
//#include <unordered_set>
#include <iomanip>
#include <stack>
#include <ctime>
#include <cassert>
#include <cmath>
#define y1 ups
#define left lll
#define right rrr
#define next nnn
//#define find fff
typedef unsigned long long ull;
using namespace std;
//mt19937_64 twister(chrono::steady_clock().now().time_since_epoch().count());
mt19937_64 twister(8888);
long long rnd(long long l, long long r)
{
uniform_int_distribution<long long> dis(l, r);
return dis(twister);
}
const int mod = (int)1e9 + 9;
//const int mod[2] = {(int)1e9 + 7, (int)1e9 + 9};
//const int st[2] = {887, 8887};'
const int maxn = 588;
const int inf = 1e4 + 88;
const int logn = 22;
const int maxa = 500*500 + 88;
const int block = 775;
const long long infll = 1e18 + 88;
const char sgl[5] = {'a', 'e', 'i', 'o', 'u'};
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int knightx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int knighty[] = {-1, 1, -2, 2, -2, 2, -1, 1};
const int kingx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int kingy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
const char sep = 'a' - 1;
const double eps = 1e-9;
const int maxn1 = 1e3 + 88;
//#define int long long
int a[588];
int ans[maxa], dp[maxa];
int all_sum;
vector<int> v;
int msum(int a, int b)
{
return (a + b)%mod;
}
void add(int x)
{
all_sum += x;
for (int i = maxa - x - 1; i >= 0; i--)
dp[i + x] = msum(dp[i + x], dp[i]);
}
void del(int x)
{
all_sum -= x;
for (int i = 0; i + x < maxa; i++)
dp[i + x] = msum(dp[i + x], mod - dp[i]);
}
void solve()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ifstream cin("bootfall.in");
ofstream cout("bootfall.out");
int n, i, j;
cin >> n;
dp[0] = 1;
for (i = 0; i < n; i++)
{
cin >> a[i];
add(a[i]);
}
if ((all_sum&1) || dp[all_sum >> 1] == 0)
{
cout << 0;
return;
}
for (i = 1; i < maxa; i++)
ans[i] = true;
for (i = 0; i < n; i++)
{
del(a[i]);
for (j = 1; j < maxa; j++)
if (((all_sum + j)&1) || dp[(all_sum + j) >> 1] == 0)
ans[j] = false;
add(a[i]);
}
for (i = 0; i < maxa; i++)
if (ans[i])
v.push_back(i);
cout << v.size() << "\n";
for (i = 0; i < v.size(); i++)
cout << v[i] << " ";
}
//#undef int
int main()
{
// srand(time(0));
// srand(8);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// ifstream cin("input.txt");
// ofstream cout("output.txt");
// ifstream cin("output.txt");
// ifstream fin("12.out");
// int a, b, i = 0;
// while (cin >> a)
// {
// fin >> b;
// if (a != b)
// {
// cout << i << " " << a << " " << b;
// return 0;
// }
// i++;
// }
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// freopen("f.in", "r", stdin);
// freopen("f.out", "w", stdout);
// int t = 10000;
// while (t--)
// {
// if (t == 9947)
// t = 9947;
// gen();
// cout << t << endl;
// brut();
// if (!solve())
// {
// cout << "kek";
// return 0;
// }
// }
solve();
return 0;
}
Compilation message
bootfall.cpp: In function 'void solve()':
bootfall.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < v.size(); i++)
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
4080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
4080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
4080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
4080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
4080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
4080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
