Submission #343381

#	Time	Username	Problem	Language	Result	Execution time	Memory
343381		Kalashnikov	Bootfall (IZhO17_bootfall)	C++17	65 / 100	1085 ms	7900 KiB

bootfall

#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
 
using namespace std;
using ll = long long;
 
const int N = 500+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7 , P = 6547;

int a[N];
int ord[500*260];

bitset<500*260> dp[N];


void solve() {
	int n;
	cin >> n;
	int sum = 0;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		sum += a[i];
	}
	set<int> st;
	for(int i = 0; i <= n; i ++) {
		for(int j = 1; j <= n; j ++) {
			if(i == j) continue;
			dp[i] = (dp[i] | (dp[i] << a[j]));
			dp[i][a[j]] = 1;
		}
	}
	if(sum%2 || !dp[0][sum/2]) {
		cout << 0;
		return;
	}
	vector<int> ans;
	for(int i = 0; i < 500*260; i ++) ord[i] = i;
	random_shuffle(ord , ord+500*260);
	for(int i1 = 0; i1 < 500*260 && i1 < (int)(1e8/n); i1 ++) {
		int i = ord[i1];
		int ok = 1;
		for(int j = 1; j <= n; j ++) {
			int cur = sum-a[j]+i;
			if(cur%2 || !dp[j][cur/2]) {
				ok = 0;
				break;
			}
		}
		if(ok) ans.push_back(i);
	}
	sort(all(ans));
	cout << ans.size() << '\n';
	for(auto to: ans) {
		cout << to << ' ';
	}
}
/*
5 5 5 5  15

*/
main() {
	file("subsequence");
    ios;
    int tt = 1;
    //cin >> tt;
    while(tt --) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

bootfall.cpp:66:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main() {
      |      ^
bootfall.cpp: In function 'int main()':
bootfall.cpp:4:48: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
    4 | #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
      |                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
bootfall.cpp:67:2: note: in expansion of macro 'file'
   67 |  file("subsequence");
      |  ^~~~
bootfall.cpp:4:77: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
    4 | #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
      |                                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:67:2: note: in expansion of macro 'file'
   67 |  file("subsequence");
      |  ^~~~

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