Submission #532851

#	Time	Username	Problem	Language	Result	Execution time	Memory
532851		hhhhaura	Table Tennis (info1cup20_tabletennis)	C++14	72 / 100	3048 ms	12444 KiB

tabletennis

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)

#ifdef wiwihorz
#define print(a...) cerr<<"Line "<<__LINE__<<":",kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L)==R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);} 
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> a(n + k + 1, 0);
	rep(i, 1, n + k) cin >> a[i];
	auto solve = [&](int l, int r, int val, int cost) {
		unordered_map<int, int> cnt;
		vector<int> ans;
		rep(i, l, r) cnt[a[i]] ++;
		for(auto i : cnt) if(i.x * 2 < val) {
			if(cnt.find(val - i.x) == cnt.end()) {
				cost -= i.y;
				continue;
			}
			int L = i.y, R = cnt[val - i.x];
			cost -= max(L, R) - min(L, R);
			rep(j, 1, min(L, R)) if(ans.size() < n) {
				ans.push_back(i.x);
				ans.push_back(val - i.x);
			}
		}
		if(val % 2 == 0) {
			int tot = cnt[val / 2];
			rep(i, 1, tot / 2) if(ans.size() < n) {
				ans.push_back(val / 2);
				ans.push_back(val / 2);
			}
			if(tot & 1) cost --;
		}
		if(cost < 0) ans.clear();
		sort(all(ans));
		return ans;
	};
	rep(i, 0, k) rep(j, 0, k - i) {
		int val = a[i + 1] + a[n + k - j];
		vector<int> ans = solve(i + 1, n + k - j, val, k - i - j);
		if(ans.size() == n) {
			rep(cur, 0, n - 1) cout << ans[cur] << " \n"[cur + 1 == n];
			return 0;
		}
	}
	assert(0);
	return 0;
}

Compilation message (stderr)

tabletennis.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
tabletennis.cpp:21:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L)==R], ++L;}
      |             ^~~~
tabletennis.cpp:21:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L)==R], ++L;}
      |                     ^~~~
tabletennis.cpp: In lambda function:
tabletennis.cpp:47:39: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   47 |    rep(j, 1, min(L, R)) if(ans.size() < n) {
      |                            ~~~~~~~~~~~^~~
tabletennis.cpp:54:37: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   54 |    rep(i, 1, tot / 2) if(ans.size() < n) {
      |                          ~~~~~~~~~~~^~~
tabletennis.cpp: In function 'int main()':
tabletennis.cpp:67:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   67 |   if(ans.size() == n) {
      |      ~~~~~~~~~~~^~~~

• Subtask 1: 11 / 11
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 9 / 9
• Subtask 6: 14 / 14
• Subtask 7: 0 / 15
• Subtask 8: 0 / 13