Submission #1159155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159155		MisterReaper	Bootfall (IZhO17_bootfall)	C++20	13 / 100	1028 ms	1888 KiB

bootfall

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(270) + 5;
constexpr int max_A = max_N;
constexpr int UB = max_N * max_A;

using B = std::bitset<UB + 1>;

B pre[max_N], suf[max_N];

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

    int N;
    std::cin >> N;
    std::vector<int> A(N + 1);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }

    std::sort(A.begin(), A.begin() + N, std::greater());

    bool bo[2] {};
    for (int i = 0; i < N; ++i) {
        bo[A[i] & 1] = true;
    }
    if (bo[0] && bo[1]) {
        std::cout << "0\n";
        return 0;
    } else if (N == 1) {
        std::cout << "0\n";
        return 0;
    }

    pre[0][0] = true;
    for (int i = 0; i < N; ++i) {
        pre[i + 1] = pre[i] | (pre[i] << A[i]);
    }
    suf[N][UB] = true;
    for (int i = N - 1; i >= 0; --i) {
        suf[i] = suf[i + 1] | (suf[i + 1] >> A[i]);
    }

    N++;
    int sum = std::accumulate(A.begin(), A.end(), 0);

    #ifdef DEBUG
        for (int i = 0; i < N; ++i) {
            std::cerr << "pre:";
            for (int j = 0; j <= UB; ++j) {
                if (pre[i][j]) {
                    std::cerr << ' ' << j;
                }
            }
            std::cerr << '\n';
        }
        for (int i = N - 1; i >= 0; --i) {
            std::cerr << "suf:";
            for (int j = 0; j <= UB; ++j) {
                if (suf[i][j]) {
                    std::cerr << ' ' << j - UB;
                }
            }
            std::cerr << '\n';
        }
    #endif

    auto check = [&]() -> bool {
        B magic[2] {};
        int cur[2] {};
        for (int i = 0; i < N - 1; ++i) {
            int nsum = sum - A[i];
            if (nsum & 1) {
                return false;
            }
            int need = nsum >> 1;
            while (cur[0] <= need) {
                magic[0].set(cur[0]);
                cur[0]++;
            }
            while (cur[1] <= need - A[N - 1]) {
                magic[1].set(cur[1]);
                cur[1]++;
            }
            bool good = false;
            if (need <= UB && (pre[i] & (suf[i + 1] >> (UB - need)) & magic[0]).count()) {
                good = true;
            }
            if (need - A[N - 1] <= UB && (pre[i] & (suf[i + 1] >> (UB - (need - A[N - 1]))) & magic[1]).count()) {
                good = true;
            }
            // for (int k = 0; k <= need; ++k) {
            //     if (pre[i][k] && suf[i + 1][need - k]) {
            //         good = true;
            //         break;
            //     }
            //     if (k <= need - A[N - 1] && pre[i][k] && suf[i + 1][need - k - A[N - 1]]) {
            //         good = true;
            //         break;
            //     }
            // }
            if (!good) {
                return false;
            }
        }
        return true;
    };

    std::vector<int> ans;
    for (int i = bo[0] ? 0 : 1; i <= sum; i += 2) {
        A[N - 1] = i;
        if (~sum & 1 && pre[N - 1][sum >> 1]) {
            sum += i;
            if (check()) {
                ans.emplace_back(i);
            }
            sum -= i;
        }
        A[N - 1] = 0;
    }

    std::cout << ans.size() << '\n';
    for (auto i : ans) {
        std::cout << i << " \n"[i == ans.back()];
    }

    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