Submission #899539

#	Time	Username	Problem	Language	Result	Execution time	Memory
899539		marcid	Bootfall (IZhO17_bootfall)	C++17	100 / 100	255 ms	22500 KiB

bootfall

//credits to Sunnatov
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define vi vector<int>
#define ii pair<int,int>
#define vii vector<ii>
#define vb vector<bool>
#define pb push_back
#define eb emplace_back
const int maxn = 25e4+5;
const int sq = 23;
const int inf = 1e18;

void solve() {
    int n; cin >> n;
    int sum = 0;
    vi a(n);
    for (int &i : a) cin >> i, sum+=i;
    set<int> ans;
    bitset<maxn> bs; 
    bs.set(0);
    vector<bitset<maxn>> without(sq), without2(n);
    for (int i : a) bs |= bs << i; //if we can make x, without a[i], we can make x+a[i] with a[i]
    for (int i = 0; i < sq; i++) {
        without[i].set(0);
        for (int j = 0; j < n; j++) {
            if (i*sq <= j && j < (i+1)*sq) continue; //if the block has j-th element, we skip
            without[i] |= without[i] << a[j]; //storing all sums we can get without block of a[j]
        }
    } for (int i = 0; i < n; i++) { //now we do the same thing for each element in each block
        without2[i] = without[i/sq]; //we restore for each block
        for (int j = i/sq*sq; j < min(n,(i/sq+1)*sq); j++) { //in this block, we store values we can get without a[i]
            if (i == j) continue;
            without2[i] |= without2[i] << a[j];
        }
    } for (int i = 1; i <= maxn; i++) { //find values that are suitable for every element of a
        if (sum&1 or !bs[sum/2]) continue;
        sum += i; bool ok = true;
        for (int j = 0; ok and j < n; j++) {
            sum -= a[j];
            if (sum&1 or !without2[j][sum/2]) ok=false;
            sum += a[j];
        }
        sum -= i;
        if (ok) ans.insert(i);
    }
    //out:
    cout<<ans.size()<<'\n';
    for(int i:ans)cout<<i<<' ';
}

signed main() {
    cin.tie()->sync_with_stdio(0);
    int tc = 1;
    //cin >> tc;
    while (tc--) {
        solve();
        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