176012025-08-08 01:37:00peti1234K-részcpp17Elfogadva 100/100174ms1004 KiB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
const int c=100005;
int n, sum, t[c], pref[c], dp[c], rossz[c]; 
vector<int> ans;
void solve() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> t[i];
        pref[i]=pref[i-1]+t[i];
        sum+=t[i];
    }

    for (int i=1; i<=n; i++) {
        dp[0]=i;
        for (int j=sum/2-t[i]; j>=0; j--) {
            dp[j+t[i]]=max(dp[j+t[i]], dp[j]);
        }
        for (int j=1; j<=i; j++) {
            int ert=pref[i]-pref[j-1], len=i-j+1;
            if (ert%2 || dp[ert/2]<j) rossz[len]=1;
        }
    }
    
    for (int i=1; i<=n; i++) {
        if (!rossz[i]) {
            ans.push_back(i);
        }
        rossz[i]=0;
    }

    cout << ans.size() << " ";
    for (auto x:ans) {
        cout << x << " ";
    }
    cout << "\n";

    ans.clear();
    for (int i=0; i<c; i++) dp[i]=0;
    sum=0;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int w;
    cin >> w;
    while (w--) {
        solve();
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask110/10
1Elfogadva2ms1004 KiB
subtask220/20
1Elfogadva2ms820 KiB
2Elfogadva4ms820 KiB
subtask370/70
1Elfogadva12ms756 KiB
2Elfogadva28ms820 KiB
3Elfogadva32ms820 KiB
4Elfogadva57ms848 KiB
5Elfogadva125ms856 KiB
6Elfogadva174ms852 KiB
7Elfogadva159ms820 KiB