Submission #1270431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270431		dang_hai_long	Bootfall (IZhO17_bootfall)	C++20	0 / 100	1 ms	832 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    vector<int> a(N+1);
    ll S = 0;
    int maxa = 0;
    for (int i = 1; i <= N; ++i) { cin >> a[i]; S += a[i]; maxa = max(maxa, a[i]); }

    int MAXS = (int)S;
    const int BSZ = 250000 + 5; // cover up to S <= 250000
    if (MAXS >= BSZ) {
        // safety, but per constraints this won't happen
        cerr << "Sum too large\n";
        return 0;
    }

    bitset<BSZ> full;
    full.reset();
    full[0] = 1;
    for (int i = 1; i <= N; ++i) full |= (full << a[i]);

    if ((S % 2LL) != 0 || !full[S/2]) {
        cout << 0 << '\n';
        return 0;
    }

    vector< bitset<BSZ> > pref(N+1), suf(N+2);
    pref[0].reset(); pref[0][0] = 1;
    for (int i = 1; i <= N; ++i) pref[i] = pref[i-1] | (pref[i-1] << a[i]);

    suf[N+1].reset(); suf[N+1][0] = 1;
    for (int i = N; i >= 1; --i) suf[i] = suf[i+1] | (suf[i+1] << a[i]);

    int LIMIT = MAXS + maxa + 5;
    vector<int> cnt(LIMIT + 1, 0);
    bitset<BSZ> Si;

    for (int i = 1; i <= N; ++i) {
        Si.reset();
        for (size_t q = suf[i+1]._Find_first(); q < (size_t)BSZ; q = suf[i+1]._Find_next(q)) {
            if ((int)q > MAXS) break;
            Si |= (pref[i-1] << (int)q);
        }
        for (size_t t = Si._Find_first(); t < (size_t)BSZ; t = Si._Find_next(t)) {
            if ((int)t > MAXS) break;
            ll x1 = 2LL * (ll)t - S + a[i];
            if (x1 > 0 && x1 <= LIMIT) ++cnt[(int)x1];
            ll x2 = S - a[i] - 2LL * (ll)t;
            if (x2 > 0 && x2 <= LIMIT) ++cnt[(int)x2];
        }
    }

    vector<int> ans;
    for (int x = 1; x <= LIMIT; ++x) if (cnt[x] == N) ans.push_back(x);

    cout << ans.size() << '\n';
    if (!ans.empty()) {
        for (size_t i = 0; i < ans.size(); ++i) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

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