Submission #1142772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142772		kitlix	Bootfall (IZhO17_bootfall)	C++20	65 / 100	1092 ms	1352 KiB

bootfall

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast,unroll-loops,inline,fast-math")
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
const int MAXN = 500;
const int MAXA = 500;
const int SZ = MAXN * MAXA + 1;
#else
const int MAXN = 20;
const int MAXA = 20;
const int SZ = MAXN * MAXA + 1;
#endif

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& el : a)
        cin >> el;
    sort(a.begin(), a.end(), greater<>());
    auto adddpp = [&](const bitset<SZ>& fw, const bitset<SZ>& bw, int a) {
        bitset<SZ> fwr;
        fwr = (fw << a) | (fw >> a);
        fwr |= (bw >> (MAXN * MAXA - a));
        bitset<SZ> bwr;
        bwr = (bw << a) | (bw >> a);
        bwr |= (fw << (MAXN * MAXA - a));
        return pair{fwr, bwr};
        };
    auto adddp = [&](const bitset<SZ>& bs, int a) {
        bitset<SZ> res;
        if (bs.count() < SZ / 1000) {
            int curi = bs._Find_first();
            while (curi != SZ) {
                if (curi < a)
                    res[a - curi] = 1;
                else
                    res[curi - a] = 1;
                if (curi + a < SZ)
                    res[a + curi] = 1;
                curi = bs._Find_next(curi);
            }
            return res;
        }
        res = (bs << a) | (bs >> a);
        int curi = bs._Find_first();
        while (curi < a) {
            res[a - curi] = 1;
            curi = bs._Find_next(curi);
        }
        return res;
        };
    bitset<SZ> cur;
    cur[0] = 1;
    for (int i = 0; i < n; ++i)
        cur = adddp(cur, a[i]);
    if (!cur[0]) {
        cout << 0;
        return 0;
    }
    bitset<SZ> ans;
    ans.set();
    // for (int i = 0; i < n; ++i) {
    //     bitset<SZ> fw, bw;
    //     fw[0] = 1, bw[MAXN * MAXA] = 1;
    //     for (int j = 0; j < n; ++j) {
    //         if (j != i) {
    //             auto res = adddpp(fw, bw, a[j]);
    //             fw = res.first;
    //             bw = res.second;
    //         }
    //     }
    //     ans &= fw;
    // }
    bitset<SZ> bs, begbs;
    begbs[0] = 1;
    for (int i = 0; i < n; ++i) {
        bs = begbs;
        for (int j = i + 1; j < n; ++j)
            bs = adddp(bs, a[j]);
        ans &= bs;
        begbs = adddp(begbs, a[i]);
    }
    vector<int> vars;
    for (int i = 1; i <= MAXN * MAXA; ++i)
        if (ans[i])
            vars.push_back(i);
    cout << vars.size() << '\n';
    for (auto el : vars)
        cout << el << ' ';
    // vector<bitset<SZ>> prefdp(n / 2), suffdp(n / 2);
    // bitset<SZ> cur;
    // cur[0] = 1;
    // for (int i = 0; i < n / 2; ++i) {
    //     cur = adddp(cur, a[i]);
    //     prefdp[i] = cur;
    // }
    // cur.reset();
    // cur[0] = 1;
    // for (int i = 0; i < n / 2; ++i) {
    //     cur = adddp(cur, a[n - 1 - i]);
    //     suffdp[i] = cur;
    // }
    // cur.reset();
    // cur[0] = 1;
    // for (int i = 0; i < n; ++i)
    //     cur = adddp(cur, a[i]);
    // if (!cur[0]) {
    //     cout << 0;
    //     return 0;
    // }
    // bitset<SZ> ans;
    // ans.set();
    // for (int i = 0; i < n; ++i) {
    //     bitset<SZ> bs;
    //     bs[0] = 1;
    //     if (i < n / 2) {
    //         if (i)
    //             bs = prefdp[i - 1];
    //         for (int j = i + 1; j < n; ++j)
    //             bs = adddp(bs, a[j]);
    //     } else {
    //         if (i != n - 1)
    //             bs = suffdp[n - 1 - (i + 1)];
    //         for (int j = i - 1; j >= 0; --j)
    //             bs = adddp(bs, a[j]);
    //     }
    //     ans &= bs;
    // }
    // vector<int> vars;
    // for (int i = 1; i <= MAXN * MAXA; ++i)
    //     if (ans[i])
    //         vars.push_back(i);
    // cout << vars.size() << '\n';
    // for (auto el : vars)
    //     cout << el << ' ';
}

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