Submission #1055046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055046		Khanhcsp2	Bootfall (IZhO17_bootfall)	C++14	100 / 100	970 ms	1364 KiB

bootfall

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define el '\n'
#define fi first
#define sc second

#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=511;
int n, a[N], sum;
bitset<N*N> bs, cur, s1, s2;
void sol()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    bs&=0;
    bs[0]=1;
    for(int i=1;i<=n;i++)
    {
        bs|=bs<<(a[i]);
        sum+=a[i];
    }
    if(sum&1 || bs[sum/2]==0)
    {
        cout << 0 << el;
        return;
    }
    int ch1=1, ch2=1;
    s1.set();
    s2.set();
    s2[0]=0;
    for(int i=1;i<=n;i++)
    {
        cur&=0;
        cur[0]=1;
        for(int j=1;j<=n;j++) if(j!=i) cur|=(cur<<(a[j]));
        int ss=sum-a[i];
        if(ss%2==0)
        {
            s2&=(cur>>(ss/2));
            if(ch1)
            {
               s1&=0;
               ch1=0;
            }
        }
        else
        {
            s1&=(cur>>(ss/2+1));
            if(ch2)
            {
                s2&=0;
                ch2=0;
            }
        }
    }
    cout << s1.count()+s2.count() << el;
    for(int i=0;i<N*N;i++)
    {
        if(s2[i]) cout << i*2 << el;
        if(s1[i]) cout << i*2+1 << el;
    }
}
signed main()
{
//    freopen("divisor.INP", "r", stdin);
//    freopen("divisor.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}

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