Submission #524875

#	Time	Username	Problem	Language	Result	Execution time	Memory
524875		boykut	Table Tennis (info1cup20_tabletennis)	C++14	100 / 100	157 ms	42240 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;
		int p = 0, l = 0, r = n + k - 1;
		while (l < r) {
			if (a[l] + a[r] > sum) p++, r--;
			else if (a[l] + a[r] < sum) p++, l++;
			else ans[anssize++] = a[l++], ans[anssize++] = a[r--];
			if (p > k) return;
		}
		if (anssize < n) return;
		sort(ans, ans + anssize);
		l = 0, r = anssize - 1;
		while (r - l + 1 > n) {
			r--; l++;
		}
		while (l <= r) {
			cout << ans[l++] << ' ';
		}
		exit(0);
	};

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

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