Submission #1264344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264344		alexistsa	Kpart (eJOI21_kpart)	C++20	10 / 100	2096 ms	1040 KiB

Main

#include <bits/stdc++.h>
using namespace std;

bool canPartitionSliding(vector<int>& window) {
    int K = window.size();
    int total = accumulate(window.begin(), window.end(), 0);
    if (total % 2 != 0) return false;
    int target = total / 2;

    unordered_map<int,int> dp;
    dp[0] = 1; // sum 0 is always possible

    // initialize first window DP
    for (int x : window) {
        unordered_map<int,int> new_dp(dp);
        for (auto& p : dp) {
            new_dp[p.first + x] += p.second;
        }
        dp = move(new_dp);
    }
    return dp.count(target);
}

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

    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        vector<int> A(n);
        for (int i=0; i<n; i++) cin >> A[i];

        vector<bool> valid(n+1, false);

        for (int K=2; K<=n; K++) {
            if (valid[K]) continue;

            bool ok = true;
            vector<int> window(A.begin(), A.begin() + K);

            if (!canPartitionSliding(window)) ok = false;

            for (int i=1; i+K<=n && ok; i++) {
                // slide window: remove A[i-1], add A[i+K-1]
                window.erase(window.begin());
                window.push_back(A[i+K-1]);
                if (!canPartitionSliding(window)) {
                    ok = false;
                    break;
                }
            }

            if (ok) {
                for (int m=K; m<=n; m+=K) valid[m] = true;
            }
        }

        vector<int> ans;
        for (int k=2; k<=n; k++) if (valid[k]) ans.push_back(k);

        if (ans.empty()) cout << -1 << "\n";
        else {
            cout<<ans.size()<<' ';
            for (int k : ans) cout << k << " ";
            cout << "\n";
        }
    }
    return 0;
}

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