Submission #890062

#	Time	Username	Problem	Language	Result	Execution time	Memory
890062		sleepntsheep	Kpart (eJOI21_kpart)	C++17	0 / 100	2027 ms	476 KiB

Main

#include <iostream>
#include <bitset>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <numeric>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using namespace std;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);

void docase()
{
    int n;
    cin >> n;
    vector<int> a(n);
    vector<long long> b;
    for (auto &x : a) cin >> x;

    inclusive_scan(ALL(a), back_inserter(b), plus<long long>(), 0ll);

    auto ok = [&](int k){
        bitset<100001> ss = 1;

        for (int i = 0; i < n; ++i)
        {
            if (i + 1 >= k) ss = ss & (ss >> a[i-k+1]);
            ss = ss | (ss << a[i]);
            if (i - k + 1 >= 0)
            {
                auto sum = b[i] - (i - k >= 0 ? b[i-k] : 0);
                //cout << i << ' ' << sum << '\n';
                if ((sum & 1) || !ss[sum >> 1]) return 0;
            }
        }

        vector<vector<int>> t(2*n);

        /*
        auto ins = [&](auto &&ins, int v, int l, int r, int x, int y, int k){
            if (r < x || y < l) return;
            if (x <= l && r <= y) { t[v].push_back(k); return; }
            auto m = midpoint(l, r), vl = v+ 1, vr = v + (m-l+1)*2;
            ins(ins, vl, l, m, x, y, k);
            ins(ins, vr, m+1, r, x, y, k);
        };

        for (int i = 0; i < n; ++i) ins(ins, 0, 0, n-1, i, i+k-1, i);

        for 
        */

        return 1;
    };

    vector<int> ans;
    for (int l = 1; l <= n; ++l) if (ok(l)) ans.push_back(l);
    cout << ans.size() << ' '; for (auto &x : ans) cout << x << ' ';
    cout << '\n';
}

int main()
{
    ShinLena;
    int T;
    cin >> T;
    while (T--) docase();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70