Submission #1055039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055039		Khanhcsp2	Bootfall (IZhO17_bootfall)	C++14	100 / 100	252 ms	33620 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 int ll
#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, pf1[N], pf2[N];
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;
    }
    pf1[0][0]=1;
    pf2[n+1][0]=1;
    for(int i=1;i<=n;i++) pf1[i]=pf1[i-1]|(pf1[i-1]<<a[i]);
    for(int i=n;i>=1;i--) pf2[i]=pf2[i+1]|(pf2[i+1]<<a[i]);
    int ch1=1, ch2=1;
    s1.set();
    s2.set();
    s2[0]=0;
    for(int i=1;i<=n;i++)
    {
        if(i<=n/2)
        {
            cur=pf2[i+1];
            for(int j=i-1;j>=1;j--) cur|=(cur<<(a[j]));
        }
        else
        {
            cur=pf1[i-1];
            for(int j=i+1;j<=n;j++) 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