Submission #1171422

#TimeUsernameProblemLanguageResultExecution timeMemory
1171422fryingducKpart (eJOI21_kpart)C++20
100 / 100
576 ms748 KiB
#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1005;
const int N = 5e4 + 5;
int n, a[maxn];
int f[N], prf[maxn];
bool ban[maxn];

void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    prf[i] = prf[i - 1] + a[i];
  }
  memset(ban, 0, sizeof(ban));
  memset(f, 0, sizeof(f));
  for (int i = 1; i <= n; ++i) {
    for (int j = N - 1; j >= a[i]; --j) {
      f[j] = max(f[j], f[j - a[i]]);
    }
    f[a[i]] = i;
    for (int k = 2; k <= i; ++k) {
      if ((prf[i] - prf[i - k]) & 1 || f[(prf[i] - prf[i - k]) / 2] <= i - k) {
        ban[k] = 1;
      }
    }
  }
  vector<int> cand;
  for (int i = 2; i <= n; ++i) {
    if (!ban[i]) cand.push_back(i);
  }
  cout << (int)cand.size() << " ";
  for (auto i : cand) cout << i << " ";
  cout << '\n';
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  int tt; cin >> tt;
  while (tt--) {
    solve();
  }

  return 0;
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...