Submission #387552

#	Time	Username	Problem	Language	Result	Execution time	Memory
387552		Kevin_Zhang_TW	Table Tennis (info1cup20_tabletennis)	C++17	100 / 100	331 ms	33140 KiB

tabletennis

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 200005;

int n, k, a[MAX_N], m;

void check(int v) {
	vector<int> ok;

	for (int i = 0, j = m-1;i < j;++i) {
		while (i < j && a[i] + a[j] > v) --j;
		if (i == j) break;
		if (a[i] + a[j] == v) {
			ok.pb(a[i]), ok.pb(a[j]);
			--j;
		}
	}

	if (ok.size() >= n) {
		ok.resize(n);

		sort(AI(ok));

		for (int i = 0;i < n;++i)
			cout << ok[i] << " \n"[i+1==n];

		exit(0);
	}
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;

	m = n + k;

	for (int i = 0;i < m;++i)
		cin >> a[i];

	int need = k;

	unordered_map<int,int> cnt;

	if (4 * k > m) {
		need = n / 2;
		for (int i = 0;i < m;++i)
			for (int j = i + 1;j < m;++j)
				++cnt[ a[i] + a[j] ];
	}
	else {
		for (int i = 0;i < 2 * k;++i)
			for (int j = 1;j <= 2 * k;++j) {
				++cnt[ a[i] + a[m-j] ];
			}
	}

	for (auto [v, c] : cnt)
		if (c >= need) 
			check(v);
}

Compilation message (stderr)

tabletennis.cpp: In function 'void check(int)':
tabletennis.cpp:34:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |  if (ok.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: 15 / 15
• Subtask 8: 13 / 13