Submission #1155401

#TimeUsernameProblemLanguageResultExecution timeMemory
1155401CiprianKpart (eJOI21_kpart)C++20
10 / 100
2096 ms480 KiB

#include <bits/stdc++.h>
using namespace std;
#define int long long 
bool deep(int sum, vector<int>&v, int l, int r){
    if(sum%2==1)return 0;
    vector<int>a;
    for(int i=l; i<=r; i++)a.push_back(v[i]);
    int n=a.size();
    
    /*vector<vector<bool>>dp(n+2, vector<bool>(sum/2+3));
    dp[0][0]=true;
    for(int i=1; i<=n; i++){
        dp[i][0]=true;
        for(int j=1; j<=sum/2; j++){
            if(j-a[i-1]>=0)dp[i][j]=(dp[i-1][j-a[i-1]]|dp[i-1][j]);
            else dp[i][j]=dp[i-1][j];
        }
    }return dp[n][sum/2];*/
    
    vector<bool>dp(sum/2+2);
    dp[0]=true;
    for(int i=0; i<n; i++){
        for(int j=sum/2; j>=0; j--){
            if(j-a[i]>=0 && dp[j-a[i]])dp[j]=true;
        }
    }return dp[sum/2];
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    vector<int>primes;
    vector<bool>cq(1001);
    for(int i=2; i<=1000; i++){
        if(!cq[i]){
            primes.push_back(i);
            for(int j=i; j<=1000; j+=i)cq[j]=true;
        }
    }
    int t;
    cin>>t;
    for(int _=0; _<t; _++){
        int n;
        cin>>n;
        vector<int>a(n+2), sum(n+2);
        for(int j=1; j<=n; j++){
            cin>>a[j];
            sum[j]=sum[j-1]+a[j];
            
        }vector<bool>check(n+1);
        /*for(int i=2; i<=n; i++){
            if(!check[i]){
            bool c=true;
            for(int j=i; j<=n; j++){
                if( !deep(sum[j]-sum[j-i], a, j-i+1, j)){
                    c=false;
                    break;
                }
            }if(c){
                for(int j=i; j<=n; j+=i){
                    check[j]=true;
                }
            }
            }
        }*/
        for(auto e: primes){
            if(e>n)break;
            if(!check[e] ){
            bool c=true;
            for(int j=e; j<=n; j++){
                if( !deep(sum[j]-sum[j-e], a, j-e+1, j)){
                    c=false;
                    break;
                }
            }if(c){
                for(int j=e; j<=n; j+=e){
                    check[j]=true;
                }
            }
            }
        }for(int i=2; i<=n; i++){
            if(!check[i]){
            bool c=true;
            for(int j=i; j<=n; j++){
                if( !deep(sum[j]-sum[j-i], a, j-i+1, j)){
                    c=false;
                    break;
                }
            }if(c){
                for(int j=i; j<=n; j+=i){
                    check[j]=true;
                }
            }
            }
        }
        vector<int>q;
        for(int i=2; i<=n; i++){
            if(check[i])q.push_back(i);
        }cout<<q.size()<<" ";
        for(auto e: q)cout<<e<<" ";
        cout<<endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...