Submission #534120

#	Time	Username	Problem	Language	Result	Execution time	Memory
534120		Deepesson	Bootfall (IZhO17_bootfall)	C++17	65 / 100	1085 ms	1088 KiB

bootfall

#include <bits/stdc++.h>
#define MAX 251000
typedef std::bitset<MAX> bits;
int main()
{
    int N;
    std::cin>>N;
    int array[N];for(auto&x:array)std::cin>>x;
    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;
        }
    }
    bits permite={};
    for(int i=0;i!=MAX;++i)permite[i]=1;
    bool poc[2]={};
    for(int i=0;i!=N;++i){
        bits prod={};
        prod[0]=1;
        long long soma=0;
        for(int j=0;j!=N;++j){
            if(i==j)continue;
            soma+=array[j];
            prod|=prod<<array[j];
        }
        poc[soma&1]=1;
        int meio = soma/2;
        permite&=prod>>meio;
    }
    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";
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 0 / 35