Submission #524859

#	Time	Username	Problem	Language	Result	Execution time	Memory
524859		boykut	Table Tennis (info1cup20_tabletennis)	C++14	72 / 100	3110 ms	489564 KiB

tabletennis

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, k;
	cin >> n >> k;
	vector<int> a(n + k);
	unordered_map<int, int> cnt;
	for (int i = 0; i < n + k; i++) {
		cin >> a[i];
		cnt[a[i]] = 1;
	}
	sort(a.begin(), a.end());

	auto check = [&](int sum) ->int {
		vector<int> ans;
		for (int i = 0; i < n + k; i++) {
			if (sum - a[i] > a[i] && cnt[sum - a[i]] == 1) {
				ans.push_back(a[i]);
				ans.push_back(sum - a[i]);
			}
		}
		if (ans.size() < n) return 0;
		sort(ans.begin(), ans.end());
		int l = 0, r = ans.size() - 1;
		while (r - l + 1 > n) {
			l++; r--;
		}
		while (l <= r) {
			cout << ans[l++] << ' ';
		}
		return 1;
	};

	if (k <= 20) {

		for (int i = 0; i <= k; i++) {
			for (int j = max(i + 1, n - 1); j < n + k; j++) {
				if (check(a[i] + a[j])) {
					return 0;
				}
			}
		}

		return 0;
	}

	map<int, int> cntsum;
	int mx = -1, sum = -1;
	for (int i = 0; i < n + k; i++) {
		for (int j = i + 1; j < n + k; j++) {
			cntsum[a[i] + a[j]]++;
			if (cntsum[a[i] + a[j]] > mx)
				mx = cntsum[a[i] + a[j]], sum = a[i] + a[j];
		}
	}

	if (check(sum));

	return 0;
}

Compilation message (stderr)

tabletennis.cpp: In lambda function:
tabletennis.cpp:27:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |   if (ans.size() < n) return 0;
      |       ~~~~~~~~~~~^~~

• 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