Submission #1095423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095423		re4ler	Table Tennis (info1cup20_tabletennis)	C++17	87 / 100	178 ms	5932 KiB

tabletennis

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define kienlian ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int mxn = 2e5 + 5;
const int maxn = 1e6 + 5;

int n, k;
int a[mxn];
int dd[mxn];
unordered_map<int, int> mp;
vector<int> ans;
vector<int> fit;

void backtrack(int id) {
	if(id > n + k) {
		vector<int> v;
		for(int i = 1; i <= n + k; i++) {
			if(dd[i]) v.push_back(a[i]);
		}
		if(v.size() != n) return;
		int l = 1;
		int r = v.size() - 2;
		int sum = v[0] + v[v.size() - 1];
		bool ok = true;
		while(l < r) {
			if(v[l] + v[r] != sum) {
				ok = false;
				break;
			}
			l++;
			r--;
		}
		if(ok) {
			for(auto i : v) cout << i << ' ';
			exit(0);
		}
		return;
	}
	for(int i = 0; i <= 1; i++) {
		dd[id] = i;
		backtrack(id + 1);
	}
}

void check(int s) {
	ans.clear();
	for(int l = 1, r = n + k; l < r; l++) {
		if(ans.size() == n) break;
		while(l < r && a[l] + a[r] > s) r--;
		if(a[l] + a[r] == s) {
			ans.push_back(a[l]);
			ans.push_back(a[r]);
			r--;
		}
	}
	if(ans.size() == n) {
		//cout << le << ' ' << ri << '\n';
		sort(ans.begin(), ans.end());
		for(auto i : ans) cout << i << ' ';
		exit(0);
	}
}

signed main() {
	kienlian
	#define taskname ""
	if (fopen(taskname".INP", "r"))
    {
        freopen(taskname".INP", "r", stdin);
        freopen(taskname".OUT", "w", stdout);
    }
    cin >> n >> k;
    for(int i = 1; i <= n + k; i++) cin >> a[i];
    sort(a + 1, a + 1 + n + k); 
	if(n + k <= 18) backtrack(1);
	else if(k == 1) {
		check(a[1] + a[n + k]);
		check(a[1] + a[n + k - 1]);
		check(a[2] + a[n + k]);
	}
	else if(k <= 100) {
		// for(int i = 1; i <= n + k; i++) cout << a[i] << ' ';
		// cout << '\n';
		for(int i = 1; i <= k + 1; i++) {
			for(int j = n + k; j >= n; j--) {
				if(i == j) continue;
				check(a[i] + a[j]);
			}
		}
	}	
	else {
		for(int i = 1; i <= 2 * k + 1; i++) {
			for(int j = n - k; j <= n + k; j++) {
				if(i == j) continue;
				mp[a[i] + a[j]]++;
			}
		}
		for(auto i : mp) if(i.second == k) fit.push_back(i.first);
		for(auto i : fit) check(i);
	}
	return 0;
}
//ditcudat
//voi2025

Compilation message (stderr)

tabletennis.cpp: In function 'void backtrack(long long int)':
tabletennis.cpp:22:15: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   22 |   if(v.size() != n) return;
      |      ~~~~~~~~~^~~~
tabletennis.cpp: In function 'void check(long long int)':
tabletennis.cpp:50:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   50 |   if(ans.size() == n) break;
      |      ~~~~~~~~~~~^~~~
tabletennis.cpp:58:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   58 |  if(ans.size() == n) {
      |     ~~~~~~~~~~~^~~~
tabletennis.cpp: In function 'int main()':
tabletennis.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(taskname".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
tabletennis.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen(taskname".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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: 0 / 13