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'
using namespace std ;
const int MN = 1e5 + 5;
int n;
namespace sub_trau{
int64_t dp[MN];
// 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);
int mn = *min_element(a.begin() + 1 , a.begin() + n + 1);
dp[0] = 1;
for ( int i = 1 ; i <= n ; i++ ){
for ( int j = sum ; j >= a[i] ; j-- ) dp[j] += dp[j - a[i]];
}
if (!dp[sum / 2] || (sum & 1)){
cout << 0;
return;
}
vector<int> ans , candidates;
for ( int i = 1 ; i <= n ; i++ ) candidates.push_back(a[i]);
for ( int val = odd ? 1 : 2 ; val <= sum - mn ; val += 2 ){
int all = sum + val;
candidates.push_back(val);
for ( int j = all ; j >= val ; j-- ) dp[j] += dp[j - val];
bool check = true;
for ( int turn = 0 ; turn < n ; turn++ ){
if (!check) break;
int need = all - candidates[turn];
if (need & 1){
check = false;
break;
}
for ( int j = candidates[turn] ; j <= need / 2 ; j++ ){
dp[j] -= dp[j - candidates[turn]];
}
if (!dp[need / 2]){
check = false;
}
for ( int j = need / 2 ; j >= candidates[turn] ; j-- ) dp[j] += dp[j - candidates[turn]];
}
if (check) ans.push_back(val);
candidates.pop_back();
for ( int j = val ; j <= all ; j++ ) dp[j] -= dp[j - val];
}
cout << ans.size() << el;
for ( auto x : ans ) cout << x << " ";
}
}
namespace sub_final{
int64_t dp[MN];
bool choose[MN];
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);
dp[0] = 1;
for ( int i = 1 ; i <= n ; i++ ){
for ( int j = sum ; j >= a[i] ; j-- ) dp[j] += dp[j - a[i]];
}
if (!dp[sum / 2] || (sum & 1)){
cout << 0;
return;
}
memset(choose , true , sizeof(choose));
for ( int i = odd ? 2 : 1 ; i <= sum ; i += 2 ) choose[i] = false;
for ( int i = 1 ; i <= n ; i++ ){
vector<int64_t> ndp(sum + 5);
for ( int j = 0 ; j <= sum ; j++ ) ndp[j] = dp[j];
for ( int j = a[i] ; j <= sum ; j++ ) ndp[j] -= ndp[j - a[i]];
for ( int val = odd ? 1 : 2 ; val <= sum ; val += 2 ){
int new_sum = sum - a[i] + val;
if ((new_sum & 1) || !ndp[new_sum / 2 - val] || (new_sum / 2 < val)) choose[val] = false;
}
}
vector<int> ans;
for ( int i = 1 ; i <= sum ; i++ ){
if (choose[i]) ans.push_back(i);
}
cout << ans.size() << el;
for ( auto x : ans ) cout << x << " ";
}
}
int32_t main (){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
if (n <= 30) sub_trau::solve();
else sub_final::solve();
}
# | 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... |