Submission #1107362

#TimeUsernameProblemLanguageResultExecution timeMemory
1107362vjudge1Kpart (eJOI21_kpart)C++17
30 / 100
2067 ms596 KiB
/** * hello * author: N29 * created: 2024-11-01 10:28:15 **/ #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3") #include<iostream> #include<vector> using namespace std; #ifndef BADGNU #pragma GCC target("sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #endif #define static_assert(...); // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> #include <tr2/dynamic_bitset> // using namespace __gnu_pbds; using namespace tr2; #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=5e4+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]; dynamic_bitset<__uint128_t> dp; bool bad[N]; void test(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; bad[i]=0; } for(int i=1;i<=n;i++){ pref[i]=pref[i-1]+a[i]; } int cnt=n; for(int i=1;i<=n;i++){ // dp.clear(); // if(cnt==0)break; dp.resize((pref[n]-pref[i-1]+1)/2+2); dp.reset(); dp[0]=1; for(int j=i;j<=n;j++){ dp=(dp|dp<<a[j]); if(bad[(j-i+1)])continue; if((pref[j]-pref[i-1])&1ll){ bad[(j-i+1)]=1; cnt--; continue; } if(!dp[(pref[j]-pref[i-1])>>1ll]){ bad[(j-i+1)]=1; cnt--; } } } vector<int>v; for(int i=1;i<=n;i++){ if(bad[i])continue; v.push_back(i); } 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...