Submission #701063

#	Time	Username	Problem	Language	Result	Execution time	Memory
701063		Ninja_Kunai	Bootfall (IZhO17_bootfall)	C++14	65 / 100	1072 ms	1248 KiB

bootfall

/**
*    Author :  Nguyen Tuan Vu
*    Created : 19.02.2023
**/

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define MASK(x) ((1ll)<<(x))
#define BIT(x, i) (((x)>>(i))&(1))
#define ALL(v)  (v).begin(), (v).end()
#define REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = "<<(val)<<"] "
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)

template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long Rand(long long l, long long r) {return l + rng() % (r - l + 1);}

void file(){
    #define TASK "GAME"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
}

const int N = 5e2 + 5;
int n, a[N];

namespace sub1 {
	const int LIM = 12 * 200 + 5;

	bitset <LIM * 2> dp, res;
	void solve() {
		sort (a + 1, a + n + 1);
		res[LIM - 5] = 1;
		FOR(i, 1, n) {
			res = (res << a[i]) | (res >> a[i]);
		}
		
		if (res[LIM - 5] == 0) return void (cout << 0);

		FOR(i, 1, n) if (a[i] != a[i - 1]) {
			dp.reset();
			dp[LIM - 5] = 1;

			FOR(j, 1, n) if (j != i) {
				dp = (dp << a[j]) | (dp >> a[j]);
			}

			if (i == 1) res = dp;
			else res = res & dp;
			if (res.count() == 0) {
				break;
			}
		}

		vector <int> ans;
		FOR(i, 0, 2 * LIM - 10) if (res[i]) ans.push_back({abs(i - (LIM - 5))});
		sort (ALL(ans)); ans.erase(unique(ALL(ans)), ans.end());
		cout << ans.size() << '\n';
		for (auto x : ans) cout << x << ' ';
	}
};

namespace sub2 {
	const int LIM = 30 * 20 + 5;

	bitset <LIM * 2> dp, res;
	void solve() {
		sort (a + 1, a + n + 1);
		res[LIM - 5] = 1;
		FOR(i, 1, n) {
			res = (res << a[i]) | (res >> a[i]);
		}
		
		if (res[LIM - 5] == 0) return void (cout << 0);

		FOR(i, 1, n) if (a[i] != a[i - 1]) {
			dp.reset();
			dp[LIM - 5] = 1;

			FOR(j, 1, n) if (j != i) {
				dp = (dp << a[j]) | (dp >> a[j]);
			}

			if (i == 1) res = dp;
			else res = res & dp;
			if (res.count() == 0) {
				break;
			}
		}

		vector <int> ans;
		FOR(i, 0, 2 * LIM - 10) if (res[i]) ans.push_back({abs(i - (LIM - 5))});
		sort (ALL(ans)); ans.erase(unique(ALL(ans)), ans.end());
		cout << ans.size() << '\n';
		for (auto x : ans) cout << x << ' ';
	}
};

namespace sub3 {
	const int LIM = 100 * 100 + 5;

	bitset <LIM * 2> dp, res;
	void solve() {
		sort (a + 1, a + n + 1);
		res[LIM - 5] = 1;
		FOR(i, 1, n) {
			res = (res << a[i]) | (res >> a[i]);
		}

		if (res[LIM - 5] == 0) return void (cout << 0);

		FOR(i, 1, n) if (a[i] != a[i - 1]) {
			dp.reset();
			dp[LIM - 5] = 1;

			FOR(j, 1, n) if (j != i) {
				dp = (dp << a[j]) | (dp >> a[j]);
			}

			if (i == 1) res = dp;
			else res = res & dp;
			if (res.count() == 0) {
				break;
			}
		}

		vector <int> ans;
		FOR(i, 0, 2 * LIM - 10) if (res[i]) ans.push_back({abs(i - (LIM - 5))});
		sort (ALL(ans)); ans.erase(unique(ALL(ans)), ans.end());
		cout << ans.size() << '\n';
		for (auto x : ans) cout << x << ' ';
	}
};

namespace sub4 {
	const int LIM = 270 * 270 + 5;

	bitset <LIM * 2> dp, res;
	void solve() {
		sort (a + 1, a + n + 1);
		res[LIM - 5] = 1;
		FOR(i, 1, n) {
			res = (res << a[i]) | (res >> a[i]);
		}
		
		if (res[LIM - 5] == 0) return void (cout << 0);

		FOR(i, 1, n) if (a[i] != a[i - 1]) {
			dp.reset();
			dp[LIM - 5] = 1;

			FOR(j, 1, n) if (j != i) {
				dp = (dp << a[j]) | (dp >> a[j]);
			}

			if (i == 1) res = dp;
			else res = res & dp;
			if (res.count() == 0) {
				break;
			}
		}

		vector <int> ans;
		FOR(i, 0, 2 * LIM - 10) if (res[i]) ans.push_back({abs(i - (LIM - 5))});
		sort (ALL(ans)); ans.erase(unique(ALL(ans)), ans.end());
		cout << ans.size() << '\n';
		for (auto x : ans) cout << x << ' ';
	}
};

namespace sub5 {
	const int LIM = 350 * 350 + 5;

	bitset <LIM * 2> dp, res;
	void solve() {
		sort (a + 1, a + n + 1);
		res[LIM - 5] = 1;
		FOR(i, 1, n) {
			res = (res << a[i]) | (res >> a[i]);
		}
		
		if (res[LIM - 5] == 0) return void (cout << 0);

		FOR(i, 1, n) if (a[i] != a[i - 1]) {
			dp.reset();
			dp[LIM - 5] = 1;

			FOR(j, 1, n) if (j != i) {
				dp = (dp << a[j]) | (dp >> a[j]);
			}

			if (i == 1) res = dp;
			else res = res & dp;
			if (res.count() == 0) {
				break;
			}
		}

		vector <int> ans;
		FOR(i, 0, 2 * LIM - 10) if (res[i]) ans.push_back({abs(i - (LIM - 5))});
		sort (ALL(ans)); ans.erase(unique(ALL(ans)), ans.end());
		cout << ans.size() << '\n';
		for (auto x : ans) cout << x << ' ';
	}
};
namespace sub6 {
	const int LIM = 500 * 500 + 5;

	bitset <LIM * 2> dp, res;
	void solve() {
		sort (a + 1, a + n + 1);
		res[LIM - 5] = 1;
		FOR(i, 1, n) {
			res = (res << a[i]) | (res >> a[i]);
		}
		
		if (res[LIM - 5] == 0) return void (cout << 0);

		FOR(i, 1, n) if (a[i] != a[i - 1]) {
			dp.reset();
			dp[LIM - 5] = 1;

			FOR(j, 1, n) if (j != i) {
				dp = (dp << a[j]) | (dp >> a[j]);
			}

			if (i == 1) res = dp;
			else res = res & dp;
			if (res.count() == 0) {
				break;
			}
		}

		vector <int> ans;
		FOR(i, 0, 2 * LIM - 10) if (res[i]) ans.push_back({abs(i - (LIM - 5))});
		sort (ALL(ans)); ans.erase(unique(ALL(ans)), ans.end());
		cout << ans.size() << '\n';
		for (auto x : ans) cout << x << ' ';
	}
};

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    file();
    cin >> n;
    FOR(i, 1, n) cin >> a[i];

    if (n <= 12 && *max_element(a + 1, a + n + 1) <= 200) sub1::solve();
    else if (n <= 30 && *max_element(a + 1, a + n + 1) <= 20) sub2::solve();
    else if (n <= 100 && *max_element(a + 1, a + n + 1) <= 100) sub3::solve();
    else if (n <= 270 && *max_element(a + 1, a + n + 1) <= 270) sub4::solve();
    else if (n <= 350 && *max_element(a + 1, a + n + 1) <= 350) sub5::solve();
    else if (n <= 500 && *max_element(a + 1, a + n + 1) <= 500) sub6::solve();
    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Compilation message (stderr)

bootfall.cpp: In function 'void file()':
bootfall.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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