Submission #874178

#	Time	Username	Problem	Language	Result	Execution time	Memory
874178		elotelo966	Bootfall (IZhO17_bootfall)	C++17	13 / 100	1063 ms	484 KiB

bootfall

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY 1000000005
#define mod 1000000007
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mid (start+end)/2
#define lim 600005
#define se second
#define fi first

inline bool ol(vector<int> &dizi,int cev){
    //vector<bool> tut(cev+5,0);
    bitset <250005> tut;
    tut[0]=1;
    bool stop=true;
    for(int i=0;i<dizi.size() && stop;i++){
        for(int j=cev/2;j>=dizi[i];j--){
            tut[j]=tut[j]|tut[j-dizi[i]];
            if(tut[cev/2]){stop=false;break;}
           // cout<<j<<" "<<tut[j]<<endl;
        }
    }
    return tut[cev/2];
}

int32_t main(){
    faster
    //freopen("bootfall.in","r",stdin);
    //freopen("bootfall.out","w",stdout);
    int n;cin>>n;
    vector<int> dizi(n);
    int cev=0;
    for(int i=0;i<n;i++){
        cin>>dizi[i];
        cev+=dizi[i];
    }
    if((cev&1) || (ol(dizi,cev))==0){
        cout<<0<<'\n';
        return 0;
    }
    vector<int> ans;
    for(int i=1;i<=cev;i++){
        vector<int> huh=dizi;
        int hum=cev;
        bool kom=1;
        for(int j=0;j<n;j++){
            huh[j]=i;
            hum+=i-dizi[j];
            if(!(hum&1))kom&=ol(huh,hum);
            else{
                kom=0;
                break;
            }
            hum=cev;
            huh[j]=dizi[j];
        }
        if(kom)ans.push_back(i);
    }
    cout<<ans.size()<<'\n';
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
    cout<<'\n';
    return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'bool ol(std::vector<long long int>&, long long int)':
bootfall.cpp:19:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i=0;i<dizi.size() && stop;i++){
      |                 ~^~~~~~~~~~~~
bootfall.cpp: In function 'int32_t main()':
bootfall.cpp:63:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=0;i<ans.size();i++){
      |                 ~^~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35