This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define el '\n'
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std ;
int n;
namespace sub_trau{
// check whether existing a way to divide array into 2 parts with sum = x;
void solve(){
vector<int> a(n + 5);
for ( int i = 1 ; i <= n ; i++ ) cin >> a[i];
if (n & 1){
cout << 0;
return;
}
bool odd = false , even = false;
for ( int i = 1 ; i <= n ; i++ ){
odd |= (a[i] & 1);
even |= (a[i] % 2 == 0);
}
if (odd && even){
cout << 0;
return;
}
int sum = accumulate(a.begin() + 1 , a.begin() + n + 1 , 0);
vector<int> ans , candidates;
for ( int i = 1 ; i <= n ; i++ ) candidates.push_back(a[i]);
for ( int val = odd ? 1 : 2 ; val <= sum ; val += 2 ){
int all = sum + val;
candidates.push_back(val);
bool check = true;
for ( int turn = 0 ; turn < n + 1 ; turn++ ){
int need = all - candidates[turn];
if (need & 1){
check = false;
break;
}
deque<int> cur;
for ( int j = 0 ; j < candidates.size() ; j++ ){
if (j == turn) continue;
cur.push_back(candidates[j]);
}
cur.push_front(-1);
vector<vector<bool>> dp(n + 5 , vector<bool> (need / 2 + 5));
dp[0][0] = 1;
for ( int i = 1 ; i <= n ; i++ ){
for ( int j = 0 ; j <= need / 2 ; j++ ){
dp[i][j] = dp[i - 1][j];
if (j >= cur[i] && dp[i - 1][j - cur[i]]){
dp[i][j] = 1;
}
}
}
if (!dp[n][need / 2]){
check = false;
break;
}
}
if (check) ans.push_back(val);
candidates.pop_back();
}
cout << ans.size() << el;
for ( auto x : ans ) cout << x << " ";
}
}
int32_t main (){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
sub_trau::solve();
}
Compilation message (stderr)
bootfall.cpp: In function 'void sub_trau::solve()':
bootfall.cpp:41:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for ( int j = 0 ; j < candidates.size() ; j++ ){
| ~~^~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |