Submission #840344

#	Time	Username	Problem	Language	Result	Execution time	Memory
840344		ASN49K	Bootfall (IZhO17_bootfall)	C++14	100 / 100	248 ms	2884 KiB

bootfall

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cmath>
#include <stack>
#include <set>
#include <functional>
#include <bitset>
#include <map>
#include <unordered_map>
#include <queue>
#include <array>
#include <numeric>
#include <complex>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, vector<A>&a) { for(auto &c:a)os<<c<<' '; return os;}
template<typename A> istream& operator>>(istream  &os, vector<A>&a) { for(auto &c:a)os>>c; return os;}
template<typename A,size_t N> istream& operator>>(istream &os, array<A,N>&a) { for(auto &c:a)os>>c; return os;}
template<typename A,typename B> istream& operator>>(istream  &os, pair<A,B>&a) { os>>a.first>>a.second; return os;}
#define bug(a) cerr << "(" << #a << ": " << a << ")\n";
#define all(x) x.begin(),x.end()
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define PQ priority_queue
using pii= pair<int,int>;
using VI= vector<int>;
using v64= vector<int64_t>;
using i64= int64_t;
using i16= int16_t;
using u64= uint64_t;
using u32= uint32_t;
using i32= int32_t;
using u16= uint16_t;
const i32 inf=1e9;
const i64 INF=1e18;
const int mod=1e9+7;
const int sigma=26;
string yn(bool x){if(x)return "YES";return "NO";}
typedef complex<double> point;
template<typename T>
void add(vector<T>&dp,const int& x)
{
    for(int i=int(dp.size())-1;i>=x;i--)
    {
        dp[i]+=dp[i-x];
    }
}
template<typename T>
void scot(vector<T>&dp,const int& x)
{
    for(int i=x;i<=int(dp.size())-1;i++)
    {
        dp[i]-=dp[i-x];
    }
}
const int N=500;
typedef bitset<N*N> bs;
//ifstream cin("bootfall.in");
//ofstream cout("bootfall.out");
void solve()
{
    int n;
    cin>>n;
    vector<int>a(n);
    cin>>a;
    int sum=accumulate(all(a),0);
    vector<u64>dp(sum+1,0);
    dp[0]=1;
    for(auto &c:a)
    {
        add(dp,c);
    }
    if(sum%2 || dp[sum/2]==0)
    {
        cout<<0;
        return;
    }
    bs sol;
    for(int i=0;i<=sum;i++)
    {
        sol[i].flip();
    }
    for(auto &c:a)
    {
        sum-=c;
        scot(dp,c);
        bs aux;
        for(int i=0;i<=sum/2;i++)
        {
            if(dp[i] > 0)
            {
                aux[sum-2*i].flip();
            }
        }
        sol&=aux;
        add(dp,c);
        sum+=c;
    }
    if(!sol.count())
    {
        cout<<0;
        return;
    }
    cout<<sol.count()<<'\n';
    for(int i=0;i<=sum;i++)
    {
        if(sol[i])
        {
            cout<<i<<' ';
        }
    }
}
main()
{
    i32 tt=1;
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cin>>tt;
    while(tt--)
    {
        solve();
    }
}

Compilation message (stderr)

bootfall.cpp:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  116 | main()
      | ^~~~

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