제출 #1329050

#제출 시각아이디문제언어결과실행 시간메모리
1329050kawhietKpart (eJOI21_kpart)C++20
30 / 100
2093 ms508 KiB
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> p(n + 1);
    for (int i = 0; i < n; i++) {
        p[i + 1] = p[i] + a[i];
    }
    auto good = [&](int k) {
        for (int i = 0; i + k <= n; i++) {
            int s = p[i + k] - p[i];
            if (s & 1) {
                return false;
            }
            int to = s / 2;
            vector<int> dp(to + 1, 0);
            dp[0] = 1;
            for (int j = i; j < i + k; j++) {
                for (int u = to; u >= a[j]; u--) {
                    if (dp[u - a[j]]) {
                        dp[u] = 1;
                    }
                    if (dp[to]) break;
                }
                if (dp[to]) break;
            }
            if (!dp[to]) {
                return false;
            }
        }
        return true;
    };
    set<int> ans;
    for (int i = 1; i <= n; i++) {
        if (ans.count(i)) {
            continue;
        }
        if (good(i)) {
            for (int j = i; j <= n; j += i) {
                ans.insert(j);
            }
        }
    }
    cout << ans.size() << ' ';
    for (auto i : ans) {
        cout << i << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...