Submission #686768

#	Time	Username	Problem	Language	Result	Execution time	Memory
686768		tolbi	Bootfall (IZhO17_bootfall)	C++17	100 / 100	959 ms	8048 KiB

bootfall

    #pragma optimize("Bismillahirrahmanirrahim")
    //█▀█─█──█──█▀█─█─█
    //█▄█─█──█──█▄█─█■█
    //█─█─█▄─█▄─█─█─█─█
    //Allahuekber
    //ahmet23 orz...
    //Sani buyuk Osman Pasa Plevneden cikmam diyor.
    //FatihSultanMehmedHan
    //YavuzSultanSelimHan
    //AbdulhamidHan
    #define author tolbi
    #include <bits/stdc++.h>
    #ifdef LOCAL
    	#include "23.h"
    #endif
    #define int long long
    #define endl '\n'
    #define vint(x) vector<int> x
    #define deci(x) int x;cin>>x;
    #define decstr(x) string x;cin>>x;
    #define cinarr(x) for (auto &it : x) cin>>it;
    #define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
    #define sortarr(x) sort(x.begin(),x.end())
    #define sortrarr(x) sort(x.rbegin(),x.rend())
    #define det(x) cout<<"NO\0YES"+x*3<<endl;
    #define INF LONG_LONG_MAX
    #define rev(x) reverse(x.begin(),x.end());
    #define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #define tol(bi) (1LL<<((int)(bi)))
    const int MOD = 1e9+7;
    using namespace std;
    mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
    int32_t main(){
    	ios;
    	int t=1;
    	int tno = 0;
    	if (!t) cin>>t;
    	while (t-(tno++)){
    		deci(n);
    		vint(arr(n));
    		cinarr(arr);
    		vector<int> ansarr(252323,0);
    		ansarr[0]=1;
    		int sum = 0;
    		for (int i = 0; i < n; i++){
    			sum+=arr[i];
    			for(int j = 250000; j >= arr[i]; j--){
    				ansarr[j] += ansarr[j-arr[i]];
    			}
    		}
    		if (sum%2 || ansarr[sum/2]==0){
    			cout<<0<<endl;
    			continue;
    		}
    		vector<int> kk(500001,0);
    		for (int i = 0; i < n; i++){
    			for (int j = 0; j <= 250000; j++){
    				if (ansarr[j] && j*2>=sum-arr[i]) {
    					kk[j*2-sum+arr[i]]++;
    				}
    				if (j<=250000-arr[i]) {
    					ansarr[j+arr[i]]-=ansarr[j];
    				}
    			}
    			for (int j = 250000-arr[i]; j >= 0; j--){
    				ansarr[j+arr[i]]+=ansarr[j];
    			}
    		}
    		vector<int> hueh;
    		for (int i = 1; i < kk.size(); i++){
    			if (kk[i]==n) hueh.push_back(i);
    		}
    		cout<<hueh.size()<<endl;
    		coutarr(hueh);
    	}
    }

Compilation message (stderr)

bootfall.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 |     #pragma optimize("Bismillahirrahmanirrahim")
      | 
bootfall.cpp: In function 'int32_t main()':
bootfall.cpp:70:25: 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]
   70 |       for (int i = 1; i < kk.size(); i++){
      |                       ~~^~~~~~~~~~~

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