Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <string>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <set>
- #include <cstring>
- #include <map>
- #include <cstdlib>
- #include <ctime>
- #include <cassert>
- #include <bitset>
- #define f first
- #define s second
- #define ll long long
- #define ull unsigned long long
- #define mp make_pair
- #define pb push_back
- #define vi vector <int>
- #define ld long double
- #define pii pair<int, int>
- #define y1 sda
- using namespace std;
- const int N = 502, mod1 = int(1e9) + 7, mod2 = int(1e9) + 9;
- int n,a[N];
- int s, sum;
- int dp[N * N];
- int f[N * N];
- vi ans;
- bool used[N];
- inline void add(int x){
- for(int j = sum; j >= 0; j--){
- dp[j + x] += dp[j];
- if(dp[j + x] >= mod1) dp[j + x] -= mod1;
- }
- sum += x;
- }
- inline void del(int x){
- sum -= x;
- for(int j = 0; j <= sum; j++){
- dp[j + x] += (mod1 - dp[j]);
- if(dp[j + x] >= mod1) dp[j + x] -= mod1;
- }
- }
- int main () {
- freopen("bootfall.in","r", stdin);
- freopen("bootfall.out","w", stdout);
- scanf("%d",&n);
- bool odd = 0, even = 0;
- for(int i = 1; i <= n; i++){
- scanf("%d",&a[i]);
- s += a[i];
- if(a[i] & 1) odd = 1;
- else even = 1;
- }
- if(odd && even){
- printf("0");
- return 0;
- }
- dp[0] = 1;
- for(int i = 1; i <= n; i++){
- add(a[i]);
- }
- if((s & 1) || !dp[s>>1]){
- printf("0");
- return 0;
- }
- for(int i = 1; i <= n; i++){
- if(used[a[i]]) continue;
- used[a[i]] = 1;
- del(a[i]);
- for(int j = 1; j <= s; j++){
- int cur = s - a[i] + j;
- if((cur & 1) || !dp[cur>>1]){
- f[j] = 1;
- }
- }
- add(a[i]);
- }
- for(int x = 1; x <= s; x++){
- if(!f[x]) ans.pb(x);
- }
- printf("%d\n", int(ans.size()));
- for(int i = 0; i < ans.size(); i++){
- printf("%d ", ans[i]);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment