Submission #339713

#	Time	Username	Problem	Language	Result	Execution time	Memory
339713		wwdd	Table Tennis (info1cup20_tabletennis)	C++14	100 / 100	662 ms	7376 KiB

tabletennis

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fore(b,c) for(int val0=b;val0<c;val0++)
#define forr(k,c,s) for(int k=c;k<s;k++)
#define pb push_back
#define mmp make_pair
using namespace __gnu_pbds;
using namespace std;
template<typename T>
using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long double ld;
typedef vector<vii> al;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
const int INF = 1e9;
const ll INFL = 1LL<<61;
vl fin(const vl& w, ll su, ll n) {
	ll piv = w.size()-1;
	vl ru;
	for(int i=0;i<w.size();i++) {
		while(piv > i && w[i]+w[piv] > su) {
			piv--;
		}
		if(piv <= i) {break;}
		if(ru.size() >= n) {break;}
		if(w[piv] + w[i] == su) {
			ru.push_back(w[piv]);
			ru.push_back(w[i]);
			piv--;
		}
	}
	sort(ru.begin(),ru.end());
	return ru;
}
ll test(const vl& w, ll su) {
	ll piv = w.size()-1;
	ll res = 0;
	for(int i=0;i<w.size();i++) {
		while(piv > i && w[i]+w[piv] > su) {
			piv--;
		}
		if(piv <= i) {break;}
		if(w[piv] + w[i] == su) {res++;
			piv--;
		}
	}
	return res;
}
ll qu(const vl& w, int piv, int k) {
	int env = w.size()-piv-1;
	int n = w.size()-k;
	for(int i=0;i<=k;i++) {
		if(env+i < w.size()) {
			if(test(w,w[piv]+w[env+i]) >= n/2) {
				return w[piv]+w[env+i];
			}
		}
	}
	for(int i=1;i<=k;i++) {
		if(env-i >= 0) {
			if(test(w,w[piv]+w[env-i]) >= n/2) {
				return w[piv]+w[env-i];
			}
		}
	}
	return -1;
}
int main() {
	ios::sync_with_stdio(0);cout.precision(20);cout.tie(0);cin.tie(0);
	ll n,k;
	cin >> n >> k;
	vl w,ord;
	for(int i=0;i<n+k;i++) {
		ll t;
		cin >> t;
		w.push_back(t);
		ord.push_back(i);
	}
	shuffle(ord.begin(),ord.end(),rng);
	ll res = -1;
	for(int i=0;i<n;i++) {
		ll va = qu(w,ord[i],k);
		if(va >= 0) {
			res = va;break;
		}
	}
	vl ans = fin(w,res,n);
	for(int i=0;i<n;i++) {
		if(i > 0) {cout << " ";}
		cout << ans[i];
	}
	cout << '\n';
}

Compilation message (stderr)

tabletennis.cpp: In function 'vl fin(const vl&, ll, ll)':
tabletennis.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=0;i<w.size();i++) {
      |              ~^~~~~~~~~
tabletennis.cpp:33:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   33 |   if(ru.size() >= n) {break;}
      |      ~~~~~~~~~~^~~~
tabletennis.cpp: In function 'll test(const vl&, ll)':
tabletennis.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0;i<w.size();i++) {
      |              ~^~~~~~~~~
tabletennis.cpp: In function 'll qu(const vl&, int, int)':
tabletennis.cpp:61:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   if(env+i < w.size()) {
      |      ~~~~~~^~~~~~~~~~

• 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