Submission #882711

#	Time	Username	Problem	Language	Result	Execution time	Memory
882711		Sokol080808	Bootfall (IZhO17_bootfall)	C++17	100 / 100	261 ms	3948 KiB

bootfall

#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using ll = long long;
using ull = unsigned long long;
using ld = long double;

template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2>& p) {in >> p.first >> p.second; return in;}
template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2>& p) {out << p.first << ' ' << p.second; return out;}
template<typename T> istream& operator>>(istream& in, vector<T>& v) {for (auto& x : v) in >> x; return in;}
template<typename T> ostream& operator<<(ostream& out, vector<T>& v) {for (auto& x : v) out << x << ' '; return out;}

const int MAX_INT = 2147483647;
const int mod = 1e9 + 7;

const int MAXN = 250001;
int s = 0;

int n;
int ans[MAXN] = {};
vector<int> a;
vector<int> in[1 << 13];
void add(int lq, int rq, int id, int x, int l, int r) {
    if (rq <= l || r <= lq) return;
    if (lq <= l && r <= rq) {
        in[x].push_back(id);
        return;
    }

    int m = (l + r) / 2;
    add(lq, rq, id, 2 * x + 1, l, m);
    add(lq, rq, id, 2 * x + 2, m, r);
}

void calc(int x, int l, int r, bitset<MAXN>& b) {
    bitset<MAXN> nb = b;
    for (auto id : in[x]) b |= (b << a[id]);

    if (l + 1 == r) {
        if (l == n - 1) {
            if (s % 2 == 1 || !b[s / 2]) {
                fill(ans, ans + MAXN, 0);
            }
        }
        if (l >= n && (l - n) % 2 == 0) {
            int cur = (l - n) / 2;
            for (int i = 1; i < MAXN; i++) {
                if ((s - a[cur] + i) % 2 == 1 || !b[(s - a[cur] + i) / 2]) {
                    ans[i] = 0;
                }
            }
        }
    } else {
        int m = (l + r) / 2;
        calc(2 * x + 1, l, m, b);
        calc(2 * x + 2, m, r, b);
    }

    swap(nb, b);
}

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

    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s += a[i];
    }

    for (int i = 0; i < n; i++) {
        add(0, n + 2 * i, i, 0, 0, 3 * n);
        add(n + 2 * i + 1, 3 * n, i, 0, 0, 3 * n);
    }

    fill(ans + 1, ans + MAXN, 1);
    bitset<MAXN> b;
    b[0] = 1;
    calc(0, 0, 3 * n, b);

    vector<int> good;
    for (int i = 1; i < MAXN; i++) {
        if (ans[i]) {
            good.push_back(i);
        }
    }

    cout << good.size() << '\n';
    cout << good << '\n';

    return 0;
}

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