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 MAX 251000
int array[505];
typedef std::bitset<MAX> bits;
bits permite={};
bool poc[2]={};
///Divide and Conquer
void dnc(int l,int r,int sum, bits atual){
if(l==r){
poc[sum&1]=1;
int meio = sum/2;
permite&=atual>>meio;
return;
}
int m = (l+r)/2;
///Left
{
bits lef;
lef=atual;
int newsum = sum;
for(int i=m+1;i<=r;++i){
lef|=lef<<array[i];
newsum+=array[i];
}
dnc(l,m,newsum,lef);
}
///Right
{
bits rig;
rig=atual;
int newsum = sum;
for(int i=l;i<=m;++i){
rig|=rig<<array[i];
newsum+=array[i];
}
dnc(m+1,r,newsum,rig);
}
}
int main()
{
int N;
std::cin>>N;
for(int i=0;i!=N;++i)std::cin>>array[i];
int t=0;
{
for(auto&x:array)t+=x;
if(t&1){
std::cout<<"0\n";
return 0;
}
bits x = {};
x[0]=1;
for(int i=0;i!=N;++i){
x|=x<<array[i];
}
if(!x[t/2]){
std::cout<<"0\n";
return 0;
}
}
for(int i=0;i!=MAX;++i)permite[i]=1;
bits start={};
start[0]=1;
dnc(0,N-1,0,start);
if(poc[0]==poc[1]){
std::cout<<"0\n";
return 0;
}
std::vector<int> pode;
for(int i=1;i!=MAX;++i){
if(permite[i])pode.push_back(i);
}
std::cout<<pode.size()<<"\n";
for(auto&x:pode){
std::cout<<((x*2)-(array[0]&1))<<" ";
}
std::cout<<"\n";
}
# | 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... |