Submission #532856

#	Time	Username	Problem	Language	Result	Execution time	Memory
532856		hhhhaura	Table Tennis (info1cup20_tabletennis)	C++14	87 / 100	3062 ms	4584 KiB

tabletennis

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)

#ifdef wiwihorz
#define print(a...) cerr<<"Line "<<__LINE__<<":",kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L)==R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);} 
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> a(n + k + 1, 0);
	rep(i, 1, n + k) cin >> a[i];
//	auto solve = [&](int l, int r, int val, int cost) {
//		unordered_map<int, int> cnt;
//		vector<int> ans;
//		rep(i, l, r) cnt[a[i]] ++;
//		for(auto i : cnt) if(i.x * 2 < val) {
//			if(cnt.find(val - i.x) == cnt.end()) {
//				cost -= i.y;
//				continue;
//			}
//			int L = i.y, R = cnt[val - i.x];
//			cost -= max(L, R) - min(L, R);
//			rep(j, 1, min(L, R)) if(ans.size() < n) {
//				ans.push_back(i.x);
//				ans.push_back(val - i.x);
//			}
//		}
//		if(val % 2 == 0) {
//			int tot = cnt[val / 2];
//			rep(i, 1, tot / 2) if(ans.size() < n) {
//				ans.push_back(val / 2);
//				ans.push_back(val / 2);
//			}
//			if(tot & 1) cost --;
//		}
//		if(cost < 0 || ans.size() < n) ans.clear();
//		sort(all(ans));
//		return ans;
//	};
	auto solve = [&](int l, int r, int val, int cost) {
		vector<int> ans;
		rep(i, l, r) {
			while(r - 1 > i && a[r] > val - a[i]) 
				r--, cost--;
			if(a[i] + a[r] == val) {
				ans.push_back(a[i]);
				ans.push_back(a[r]);
				r --;
			}
			else cost --;
		}
		if(cost < 0 || ans.size() < n) return vector<int>();
		while(ans.size() > n) ans.pop_back();
		sort(all(ans));
		return ans;
	};
	rep(i, 0, k) rep(j, 0, k - i) {
		int val = a[i + 1] + a[n + k - j];
		vector<int> ans = solve(i + 1, n + k - j, val, k - i - j);
		if(ans.size() == n) {
			rep(cur, 0, n - 1) cout << ans[cur] << " \n"[cur + 1 == n];
			return 0;
		}
	}
	assert(0);
	return 0;
}

Compilation message (stderr)

tabletennis.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
tabletennis.cpp:20:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L)==R], ++L;}
      |             ^~~~
tabletennis.cpp:20:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L)==R], ++L;}
      |                     ^~~~
tabletennis.cpp: In lambda function:
tabletennis.cpp:75:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |   if(cost < 0 || ans.size() < n) return vector<int>();
      |                  ~~~~~~~~~~~^~~
tabletennis.cpp:76:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |   while(ans.size() > n) ans.pop_back();
      |         ~~~~~~~~~~~^~~
tabletennis.cpp: In function 'int main()':
tabletennis.cpp:83:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |   if(ans.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: 0 / 13