Submission #387599

#	Time	Username	Problem	Language	Result	Execution time	Memory
387599		8e7	Table Tennis (info1cup20_tabletennis)	C++14	100 / 100	181 ms	3136 KiB

tabletennis

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define ll long long
#define maxn 160005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//find by order, order of key
int a[maxn];
vector<int> ans;
bool solve(int x, int tot, bool rec, int v, int k) {
	int ret = 0, ind = tot - 1, bad = 0;
	for (int i = 0;i < tot;i++) {
		while (ind >= 0 && a[i] + a[ind] > x) {
			ind--;
		}
		if (ind < i) break;
		if (ind != i && a[i] + a[ind] == x) {
			ret++;
			if (i < ind && rec) ans.push_back(a[i]), ans.push_back(a[ind]);
		} else {
			bad++;
			if (bad > k) return false;
		}
		if (ret == v) {
			return true;
		}
	}
	return false;
}
int main() {
	io
	int n, k;
	cin >> n >> k;
	for (int i = 0;i < n + k;i++) cin >> a[i];
	for (int i = 0;i <= k;i++) {
		for (int j = n + k - 1;j >= n + i - 1;j--) {
			if (i >= j) continue;
			if (solve(a[i] + a[j], n + k, false, n / 2, k)) {
				solve(a[i] + a[j], n + k, true, n / 2, k);
				sort(ans.begin(), ans.end());
				for (int x:ans) cout << x << " ";
				cout << "\n";
				return 0;
			}
		}
	}
}
/*
4 3
1 2 3 4 8 10 20

4 2
1 2 3 4 5 6
 */

• 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: 15 / 15
• Subtask 8: 13 / 13