Submission #524862

#	Time	Username	Problem	Language	Result	Execution time	Memory
524862		boykut	Table Tennis (info1cup20_tabletennis)	C++14	72 / 100	3109 ms	494268 KiB

tabletennis

#include <bits/stdc++.h>

using namespace std;

int ans[300000], anssize;

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());

	function<void(int)> check = [&](int sum) {
		anssize = 0;
		for (int i = 0; i < n + k; i++) {
			if (sum - a[i] > a[i] && cnt[sum - a[i]] == 1) {
				ans[anssize++] = a[i];
				ans[anssize++] = sum - a[i];
			}
		}
		if (anssize < n) return;
		sort(ans, ans + anssize);
		int l = 0, r = anssize - 1;
		while (r - l + 1 > n) {
			l++; r--;
		}
		while (l <= r) {
			cout << ans[l++] << ' ';
		}
		exit(0);
	};

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

	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];
		}
	}

	check(sum);

	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