Submission #788925

#	Time	Username	Problem	Language	Result	Execution time	Memory
788925		vjudge1	Bootfall (IZhO17_bootfall)	C++17	0 / 100	1 ms	212 KiB

bootfall

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define SQ									   350
#define endl                                   '\n'
#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define PQ                                     priority_queue
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define ios				                       ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y)	                       freopen(x, "r", stdin); freopen(y, "w", stdout);

const int N = 2e5+25, lg=18;
int Mod = 1e9+23;
//ll Mod = 998244353;

ll max(ll a, ll b)                             {return (a>b ? a : b);}
ll min(ll a, ll b)                             {return (a<b ? a : b);}
ll abso(ll a)                                  {return (a<0?-a:a);}
inline int MOD(int a, int mod=Mod) {
	while(a < 0) a += mod;
	while(a>=mod) a-=mod;
	return a;
}
inline ll poww(ll a, ll b) {
    ll ans = 1;
    a=MOD(a);
    while (b) {
        if (b & 1) ans = MOD(ans*a);
        b >>= 1;
        a = MOD(a*a);
    }
    return ans;
}

int n, A[N], dp[505*505], tmp[505*505], num[N], B[N], sum, z;
int tmp2=0;
int main () {
	//ios;
	
	file_io("input.txt", "output.txt");

	cin>>n;
	for(int i=1; i<=n; i++) {A[i] = 0;}
	for(int i=1; i<=n; i++) {
		try {
			cin>>A[i]; 
			//cout<<i;
			//cout<<A[500]<<endl;
			//tmp2 = A[i];
			B[i] = A[i];
		} catch(const exception & ex) {
			cout<<ex.what()<<endl;
		}
	}
	for(int i=1; i<=n; i++) tmp2 += B[i];
	for(int i=1; i<n; i++) if(MOD(A[i]%2, 2)!=MOD(A[i+1]%2, 2)) z = 1;
	if(z || MOD(tmp2%2, 2)==1) kill(0);

	dp[0] = 1;
	for(int i=1; i<=n; i++) {
		for(int j=tmp2; j>=A[i]; j--) {
			dp[j] = MOD(dp[j] + dp[j-A[i]]);
		}
	}


	for(int i=1; i<=n; i++) {
		for(int j=A[i]; j<=tmp2; j++) {
			tmp[j] = dp[j];
			dp[j] = MOD(dp[j] - dp[j-A[i]]);
		}
		for(int f=MOD(A[1]%2, 2); f<=tmp2; f+=2) {
			if(dp[(f+tmp2-A[i])/2]>0) num[f]++;
		}
		for(int j=tmp2; j>=A[i]; j--) dp[j] = tmp[j];
	}

	vector<int> ans;
	for(int i=1; i<=tmp2; i++) {
		if(num[i]==n && dp[tmp2/2]>0) ans.pb(i);
	}

	cout<<size(ans)<<endl;
	for(auto i : ans) {cout<<i<<' ';}

	return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:33:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 | #define file_io(x,y)                        freopen(x, "r", stdin); freopen(y, "w", stdout);
      |                                             ~~~~~~~^~~~~~~~~~~~~~~
bootfall.cpp:63:2: note: in expansion of macro 'file_io'
   63 |  file_io("input.txt", "output.txt");
      |  ^~~~~~~
bootfall.cpp:33:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 | #define file_io(x,y)                        freopen(x, "r", stdin); freopen(y, "w", stdout);
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~
bootfall.cpp:63:2: note: in expansion of macro 'file_io'
   63 |  file_io("input.txt", "output.txt");
      |  ^~~~~~~

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