Submission #173200

#	Time	Username	Problem	Language	Result	Execution time	Memory
173200		DeD_TihoN	Bootfall (IZhO17_bootfall)	C++14	13 / 100	1055 ms	6168 KiB

bootfall

#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define ull unsigned long long
#define endl '\n'
#define y1 yaumru
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define iter vector<int>::iterator
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=500+2;
const int inf=1e9+1e9;
const int mod=1e9+7;
const ld eps=1e-9;
const int M=250000+1;

bitset<M>dp[N];
bitset<M>pref[N];
bitset<M>suf[N];
int a[N];

main ()
{
    ios;
    int n;
    cin>>n;
    for (int i=1;i<=n;++i){
        cin>>a[i];
    }
    int sum=0;
    for (int i=1;i<=n;++i){
        sum+=a[i];
    }
    if (sum%2==1){
        cout<<0<<endl;
        exit(0);
    }
    pref[0][0]=1;
    suf[n+1][0]=1;
    for (int i=1;i<=n;++i){
        pref[i]=(pref[i-1]|(pref[i-1]<<a[i]));
    }
    for (int i=n;i>=1;--i){
        suf[i]=(suf[i+1]|(suf[i+1]<<a[i]));
    }
    for (int i=0;i<=n;++i){
        dp[i]=suf[i+1];
        if (i!=0){
            for (int j=pref[i-1]._Find_first();j<M;j=pref[i-1]._Find_next(j)){
                bitset<M>f=(suf[i+1]<<j);
                dp[i]=(dp[i]|f);
            }
        }
    }
//    for (int j=0;j<=10;++j){
//        cout<<dp[0][j]<<' ';
//    }
    vector<int>ans;
    if (dp[0][sum/2]==0){
        cout<<0<<endl;
        exit(0);
    }
    for (int i=1;i<=M;++i){
        bool cc=true;
        for (int j=1;j<=n;++j){
            if ((sum-a[j]+i)%2==1){
                cc=false;
                break;
            }
            if ((sum-a[j]+i)%2==0){
                if (dp[j][(sum-a[j]+i)/2]==0){
                    cc=false;
                    break;
                }
            }
        }
        if (cc)ans.pb(i);
    }
    cout<<(int)ans.size()<<endl;
    for (int i=0;i<ans.size();++i){
        cout<<ans[i]<<' ';
    }
}

Compilation message (stderr)

bootfall.cpp:43:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^
bootfall.cpp: In function 'int main()':
bootfall.cpp:101:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<ans.size();++i){
                  ~^~~~~~~~~~~

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