Submission #464881

#	Time	Username	Problem	Language	Result	Execution time	Memory
464881		TeaTime	Bootfall (IZhO17_bootfall)	C++17	0 / 100	23 ms	49868 KiB

bootfall

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <bitset>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

#define int ll
const ll INF = 1e9, SZ = 510 * 510, SZ2 = 510;

ll n;
vector<ll> vec;
bitset<SZ> bts;
bitset<SZ> pref[SZ2], suf[SZ2], un[SZ2];
vector<ll> svd[SZ2 * 4];
bitset<SZ> cur[SZ2 * 4];

void psh(int v, int l, int r, int askl, int askr, int val) {
    if (askr <= askl) return;
    if (l >= askr || r <= askl) return;

    if (askl <= l && r <= askr) {
        svd[v].push_back(val);
        return;
    }

    int mid = (l + r) / 2;
    psh(v * 2 + 1, l, mid, askl, askr, val);
    psh(v * 2 + 2, mid, r, askl, askr, val);
}

void build(int v, int l, int r) {
    for (auto c : svd[v]) cur[v] |= (cur[v] << c);
    if (l == r - 1) {
        un[l] = cur[v];
    } else {
        int mid = (l + r) / 2;
        cur[v * 2 + 1] = cur[v];
        cur[v * 2 + 2] = cur[v];
        build(v * 2 + 1, l, mid);
        build(v * 2 + 2, mid, r);
    }
}
signed main() {
    fastInp;

    cin >> n;
    vec.resize(n);

    for (auto& c : vec) cin >> c;

    bts[0] = 1;
    ll sm = 0;

    pref[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        psh(0, 0, SZ2, 0, i, vec[i - 1]);
        psh(0, 0, SZ2, i, SZ2, vec[i - 1]);
        pref[i] = (pref[i - 1] | (pref[i - 1] << vec[i - 1]));
    }

    suf[n][0] = 1;
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = (suf[i + 1] | (suf[i + 1] << vec[i]));
    }

    cur[0][0] = 1;
    build(0, 0, SZ2);
   /* for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < SZ; j++) {
            if (pref[i][j]) un[i] |= (suf[i + 1] << j);
        }
    }*/

    for (auto c : vec) {
        sm += c;
        bts |= (bts << c);
    }

    if (sm % 2) {
        cout << "0";
        return 0;
    }

    if (bts[sm / 2] != 1) {
        cout << "0";
        return 0;
    }

    vector<ll> ans;

    for (int i = 1; i < SZ; i++) {
        bool f = 1;
        for (int j = 0; j < n; j++) {
            ll cursm = sm - vec[j] + i;
            if (cursm % 2) {
                f = 0;
                break;
            }

            cursm /= 2;
            if (i > cursm) {
                f = 0;
                break;
            }

            if (!un[j][cursm - i]) {
                f = 0;
                break;
            }
        }

        if (f) ans.push_back(i);
    }

    cout << ans.size() << "\n";
    for (auto c : ans) cout << c << " ";
   
    return 0;
}

/*
3 4
RGWR
GRGG
RGWW

4 4
RGWR
GRRG
WGGW
WWWR

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
*/

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