Submission #1264327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264327		alexistsa	Kpart (eJOI21_kpart)	C++20	0 / 100	826 ms	480 KiB

Main

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

// Function to check if array segment can be partitioned into 2 equal-sum subsequences
bool canPartition(const vector<int>& arr) {
    int sum = accumulate(arr.begin(), arr.end(), 0);
    if (sum % 2 != 0) return false; // must be even
    int target = sum / 2;

    bitset<10001> dp; // adjust size if needed
    dp[0] = 1;
    for (int x : arr) {
        dp |= (dp << x);
        if (target < (int)dp.size() && dp[target]) return true; // early exit
    }
    return dp[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; // already marked as multiple of smaller K

            bool ok = true;
            for (int i=0; i+K<=n; i++) {
                vector<int> window(A.begin()+i, A.begin()+i+K);
                if (!canPartition(window)) { ok = false; break; }
            }

            if (ok) {
                // mark all multiples of K as valid
                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 {
            for (int k : ans) cout << k << " ";
            cout << "\n";
        }
    }
    return 0;
}

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