Submission #1288587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288587		the_ZHER	Kpart (eJOI21_kpart)	C++17	30 / 100	2095 ms	576 KiB

Main

#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int inf=1e18;
const int N=2e5+100;
const int N1=5e5;
const int N2=1e6+100;
const int mod=1e9+7;
const int k1=447;
struct edge{
    int id,cnt,x;
};
struct edge1{
    int a,b,x,id;
};
bool cmp(pair<int,int> a,pair<int,int> b){
    if(a.first-a.second==b.first-b.second){
        return a.first<b.first;
    }
    return a.first-a.second<b.first-b.second;
}
bool cmp1(edge1 a,edge1 b){
    return a.x<b.x;
}
vector<int>v;
int dp[N];
int sum;
int sum1;
void add(int x){
    sum1+=x;
    for(int i=sum;i>=x;i--){
        dp[i]+=dp[i-x];
    }
}
void del(int x){
    sum1-=x;
    for(int i=x;i<=sum;i++){
        dp[i]-=dp[i-x];
    }
}
signed main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
boost; 
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        v.push_back(0);
        sum=0;
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            sum+=x;
            v.push_back(x);
        }
        sum1=0;
        vector<int>ans;
        for(int i=2;i<=n;i++){
            int l=1;
            int ok=0;
            dp[0]=1;
            sum1=0;
            for(int j=1;j<=n;j++){
                if(j<=i){
                    add(v[j]);
                    if(j==i){
                        if(dp[sum1/2]==0||sum1%2==1){
                            ok=1;
                            break;
                        }
                    }
                    continue;
                }
                del(v[l]);
                add(v[j]);
                l++;
                if(dp[sum1/2]==0||sum1%2==1){
                    ok=1;
                    break;
                }
            }
            if(ok==0){
                ans.push_back(i);
            }
            for(int j=0;j<=sum;j++){
                dp[j]=0;
            }
        }
        cout<<ans.size()<<" ";
        for(int i=0;i<ans.size();i++){
            cout<<ans[i]<<" ";
        }
        ans.clear();
        cout<<"\n";
        v.clear();
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70