Submission #1107281

#TimeUsernameProblemLanguageResultExecution timeMemory
1107281vjudge1Kpart (eJOI21_kpart)C++17
10 / 100
2054 ms504 KiB
/** * hello * author: N29 * created: 2024-11-01 10:28:15 **/ #include<bits/stdc++.h> using namespace std; #ifndef BADGNU #pragma GCC target("sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #endif #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ll long long #define int ll #define ld long double #define y1 cheza mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; template<class T> using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>; const int N=1e5+100; const int M=5001; const int B=447; const int mod=998244353; const ll INF=1e18; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; const double eps=1e-6; int n; int a[N]; int pref[N]; bitset<N> dp; bool check(int l,int r){ dp.reset(); dp[0]=1; int sum=pref[r]-pref[l-1]; if(sum%2)return 0; for(int i=l;i<=r;i++){ dp=(dp|(dp<<a[i])); } sum/=2; return dp[sum]; } void test(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ pref[i]=pref[i-1]+a[i]; } vector<int>v; for(int k=2;k<=n;k++){ v.push_back(k); for(int i=1;i+k-1<=n;i++){ int j=i+k-1; if(!check(i,j)){ v.pop_back(); break; } } } cout<<v.size()<<' '; for(auto i:v){ cout<<i<<' '; } cout<<'\n'; } /* */ signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr); int t2=1; cin>>t2; for(int i=1;i<=t2;i++){ test(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...