Submission #978855

#TimeUsernameProblemLanguageResultExecution timeMemory
978855VMaksimoski008Kpart (eJOI21_kpart)C++17
30 / 100
2043 ms516 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt") void solve() { int n; cin >> n; vector<int> v(n+1); for(int i=1; i<=n; i++) cin >> v[i]; vector<bool> ans(n+1, 1); for(int i=1; i<=n; i++) { bitset<100001> bs; bs[0] = 1; ll sum = 0; for(int j=i; j<=n; j++) { sum += v[j]; bs |= (bs << v[j]); if(sum % 2 == 1 || !ans[j-i+1]) { ans[j-i+1] = 0; continue; } if(!bs[sum/2]) ans[j-i+1] = 0; } } vector<int> res; for(int i=1; i<=n; i++) if(ans[i]) res.push_back(i); cout << res.size() << " "; for(int &x : res) cout << x << " "; cout << '\n'; } int main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int t = 1; 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...