제출 #1270432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270432		dang_hai_long	Bootfall (IZhO17_bootfall)	C++20	13 / 100	1092 ms	15728 KiB

bootfall

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

const int MAXS = 250000 + 5;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    if (!(cin >> N)) return 0;
    vector<int> a(N+1);
    ll S = 0;
    for (int i = 1; i <= N; ++i) { cin >> a[i]; S += a[i]; }

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

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

    vector< bitset<MAXS> > pref(N+2), 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]);

    vector< bitset<MAXS> > Si(N+1);
    for (int i = 1; i <= N; ++i) {
        Si[i].reset();
        for (int q = suf[i+1]._Find_first(); q < MAXS; q = suf[i+1]._Find_next(q)) {
            if (q > MAXS-1) break;
            Si[i] |= (pref[i-1] << q);
        }
    }

    unordered_map<ll,int> cnt; cnt.reserve(1000000);

    auto add_candidates = [&](int i){
        for (int t = Si[i]._Find_first(); t < MAXS; t = Si[i]._Find_next(t)) {
            ll x1 = 2LL * t - S + a[i];
            if (x1 > 0) cnt[x1]++; // positive
            ll x2 = S - a[i] - 2LL * t;
            if (x2 > 0) cnt[x2]++;
        }
    };

    add_candidates(1);
    for (int i = 2; i <= N; ++i) {
        unordered_map<ll,int> tmp; tmp.reserve( (size_t) (cnt.size()/2 + 10) );
        for (int t = Si[i]._Find_first(); t < MAXS; t = Si[i]._Find_next(t)) {
            ll x1 = 2LL * t - S + a[i];
            if (x1 > 0) tmp[x1] = 1;
            ll x2 = S - a[i] - 2LL * t;
            if (x2 > 0) tmp[x2] = 1;
        }
        vector<ll> to_erase;
        for (auto &pr : cnt) {
            if (tmp.find(pr.first) == tmp.end()) to_erase.push_back(pr.first);
        }
        for (ll k : to_erase) cnt.erase(k);
        if (cnt.empty()) break;
    }

    vector<ll> ans;
    ans.reserve(cnt.size());
    for (auto &pr : cnt) ans.push_back(pr.first);
    sort(ans.begin(), ans.end());
    // output
    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: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35