제출 #534148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
534148		Deepesson	Bootfall (IZhO17_bootfall)	C++17	100 / 100	62 ms	2900 KiB

bootfall

#include <bits/stdc++.h>
#define MAX 251000
int array[505];
typedef std::bitset<MAX> bits;
bits permite={};
bool poc[2]={};

///Idea!!!
///Notice that the knapsack will be very similar each time: All elements - 1 of them.
///Can we optimize mergings, considering that many times they will repeat each other???
///Of course we can!!!
///I will use divide and conquer, and in N log N operations I will be able to merge everything necessary, getting the N sets!
///Complexity: O(N^3 log N / 64)
///Around 20 million operations, very fast

///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";
}

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