//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <bitset>
using namespace std;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
typedef long long ll;
typedef long double ld;
#define int ll
const ll INF = 1e9, SZ = 510 * 510, SZ2 = 510;
ll n;
vector<ll> vec;
bitset<SZ> bts;
bitset<SZ> pref[SZ2], suf[SZ2], un[SZ2];
vector<ll> svd[SZ2 * 4];
bitset<SZ> cur[SZ2 * 4];
void psh(int v, int l, int r, int askl, int askr, int val) {
if (askr <= askl) return;
if (l >= askr || r <= askl) return;
if (askl <= l && r <= askr) {
svd[v].push_back(val);
return;
}
int mid = (l + r) / 2;
psh(v * 2 + 1, l, mid, askl, askr, val);
psh(v * 2 + 2, mid, r, askl, askr, val);
}
void build(int v, int l, int r) {
for (auto c : svd[v]) cur[v] |= (cur[v] << c);
if (l == r - 1) {
un[l] = cur[v];
} else {
int mid = (l + r) / 2;
cur[v * 2 + 1] = cur[v];
cur[v * 2 + 2] = cur[v];
build(v * 2 + 1, l, mid);
build(v * 2 + 2, mid, r);
}
}
signed main() {
fastInp;
cin >> n;
vec.resize(n);
for (auto& c : vec) cin >> c;
bts[0] = 1;
ll sm = 0;
pref[0][0] = 1;
for (int i = 1; i <= n; i++) {
psh(0, 0, SZ2, 0, i, vec[i - 1]);
psh(0, 0, SZ2, i + 1, SZ2, vec[i - 1]);
pref[i] = (pref[i - 1] | (pref[i - 1] << vec[i - 1]));
}
suf[n][0] = 1;
for (int i = n - 1; i >= 0; i--) {
suf[i] = (suf[i + 1] | (suf[i + 1] << vec[i]));
}
cur[0][0] = 1;
build(0, 0, SZ2);
/* for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < SZ; j++) {
if (pref[i][j]) un[i] |= (suf[i + 1] << j);
}
}*/
for (auto c : vec) {
sm += c;
bts |= (bts << c);
}
if (sm % 2) {
cout << "0";
return 0;
}
if (bts[sm / 2] != 1) {
cout << "0";
return 0;
}
vector<ll> ans;
for (int i = 1; i < SZ; i++) {
bool f = 1;
for (int j = 0; j < n; j++) {
ll cursm = sm - vec[j] + i;
if (cursm % 2) {
f = 0;
break;
}
cursm /= 2;
if (i > cursm) {
f = 0;
break;
}
if (!un[j][cursm - i]) {
f = 0;
break;
}
}
if (f) ans.push_back(i);
}
cout << ans.size() << "\n";
for (auto c : ans) cout << c << " ";
return 0;
}
/*
3 4
RGWR
GRGG
RGWW
4 4
RGWR
GRRG
WGGW
WWWR
5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
49868 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
49868 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
49868 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
49868 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
49868 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
25 ms |
49868 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |