Submission #524865

#	Time	Username	Problem	Language	Result	Execution time	Memory
524865		boykut	Table Tennis (info1cup20_tabletennis)	C++14	0 / 100	3095 ms	503712 KiB

tabletennis

#include <bits/stdc++.h>

using namespace std;

int ans[300000], anssize;
int a[300000], cnt[10000000];

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

	vector<int> primes = {9996859,9996887,
	9996929,9996937,9996949,9996979,9996991,9997007,9997033,9997049,9997063,9997087,
	9997093,9997109,9997123,9997129,9997133,9997177,9997189,9997201,9997219,9997237,
	9997291,9997303,9997319,9997321,9997327,9997333,9997349,9997357,9997367,9997381,
	9997397,9997441,9997451,9997483,9997517,9997523,9997573,9997577,9997579,9997583,
	9997597,9997601,9997613,9997621,9997627,9997643,9997661,9997697,9997703,9997711,
	9997739,9997747,9997753,9997777,9997783,9997787,9997817,9997829,9997831,9997859,
	9997873,9997877,9997879,9997913,9997927,9997937,9997951,9997957,9997969,9997987,
	9997991,9997997,9998017,9998033,9998099,9998117,9998119,9998129,9998141,9998143,
	9998147,9998173,9998179,9998201,9998203,9998207,9998239,9998249,9998273,9998279,
	9998281,9998309,9998321,9998323,9998333,9998377,9998381,9998393,9998413,9998423,
	9998441,9998447,9998459,9998479,9998539,9998543,9998557,9998561,9998581,9998587,
	9998603,9998623,9998633,9998641,9998689,9998699,9998701,9998719,9998741,9998743,
	9998749,9998753,9998777,9998797,9998801,9998809,9998851,9998861,9998867,9998887,
	9998893,9998903,9998929,9998969,9998971,9998977,9999047,9999049,9999053,9999071,
	9999083,9999161,9999163,9999167,9999193,9999217,9999221,9999233,9999271,9999277,
	9999289,9999299,9999317,9999337,9999347,9999397,9999401,9999419,9999433,9999463,
	9999469,9999481,9999511,9999533,9999593,9999601,9999637,9999653,9999659,9999667,
	9999677,9999713,9999739,9999749,9999761,9999823,9999863,9999877,9999883,9999889};

	int n, k;
	cin >> n >> k;
	int R = primes[rand() % primes.size()];
	for (int i = 0; i < n + k; i++) {
		cin >> a[i];
		cnt[a[i] % R] = 1;
	}
	sort(a, a + n + k);

	function<void(int)> check = [&](int sum) {
		anssize = 0;
		for (int i = 0; i < n + k; i++) {
			if (anssize == n) break;
			if (sum - a[i] <= a[i]) break;
			if (cnt[(sum - a[i]) % 9999889] == 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 (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: 0 / 11
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 9
• Subtask 6: 0 / 14
• Subtask 7: 0 / 15
• Subtask 8: 0 / 13