#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <array>
#include <bitset>
#include <cassert>
using namespace std;
const int maxn=505, Log=9, pot=(1<<Log);
bitset < maxn*maxn > potencijal;
int sum;
bitset < maxn*maxn > dp[maxn];
int n;
int br;
int tren;
int p;
void dodaj(int x){
for(int i=sum; i>=x; --i){
dp[br][i]=dp[br-1][i-x]|dp[br-1][i];
}
for(int i=0; i<x; ++i){
dp[br][i]=dp[br-1][i];
}
br++;
}
void probaj(){
if(p==2){
if((tren&1) || !dp[br-1][tren/2]){
p=0;
}
else{
p=1;
}
// cout << "hehe " << p << endl;
}
else if(p){
for(int i=1; i<sum; ++i){
if(!((i+tren)&1) && dp[br-1][(i+tren)/2]){
potencijal[i]=1;
}
}
p=0;
}
else{
for(int i=0; i<sum; i++){
if(potencijal[i] && (((i+tren)&1) || !dp[br-1][(i+tren)/2])){
potencijal[i]=0;
}
}
}
}
vector < int > t[pot*2];
void update(int L, int D, int x, int l, int d, int val){
if(L>=l && D<=d){
t[x].push_back(val);
return;
}
if((L+D)/2>=l){
update(L, (L+D)/2, x*2, l, d, val);
}
if((L+D)/2+1<=d){
update((L+D)/2+1, D, x*2+1, l, d, val);
}
}
void rokaj(int x){
for(int i=0; i<(int)t[x].size(); i++){
tren+=t[x][i];
dodaj(t[x][i]);
}
if(x>=pot){
if(p==2 || br==n){
probaj();
}
br-=t[x].size();
for(int i=0; i<(int)t[x].size(); i++){
tren-=t[x][i];
}
return;
}
rokaj(x*2);
rokaj(x*2+1);
br-=t[x].size();
for(int i=0; i<(int)t[x].size(); i++){
tren-=t[x][i];
}
}
int a[maxn];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
int par=0, nepar=0;
for(int i=0; i<n; i++){
cin >> a[i];
sum+=a[i];
if(a[i]&1){
nepar++;
}
else{
par++;
}
update(0, pot-1, 1, 0, i, a[i]);
update(0, pot-1, 1, i+2, pot, a[i]);
}
if((par && nepar) || (n&1)){
cout << 0 << '\n';
return 0;
}
if(par){
for(int i=1; i<n; i++){
if(a[i]!=a[i-1]){
cout << 0 << '\n';
return 0;
}
}
cout << n/2 << '\n';
for(int i=1; i<n; i+=2){
cout << a[0]*i << '\n';
}
}
dp[0][0]=1;
br=1;
p=2;
rokaj(1);
cout << potencijal.count() << '\n';
for(int i=0; i<(int)maxn*maxn; i++){
if(potencijal[i]){
cout << i << ' ';
}
}
cout << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |