Submission #1264335

#TimeUsernameProblemLanguageResultExecution timeMemory
1264335alexistsaKpart (eJOI21_kpart)C++20
0 / 100
2095 ms4092 KiB
#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<10000001> 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 {
            cout<<ans.size()<<endl;
            for (int k : ans) cout << k << " ";
            cout << "\n";
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...