Submission #339716

#	Time	Username	Problem	Language	Result	Execution time	Memory
339716		wwdd	Table Tennis (info1cup20_tabletennis)	C++14	100 / 100	470 ms	44880 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;
}
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);
	}
	ll res = -1;
	map<ll,ll> bs;
	ll lim = min(ll(w.size()),2*k);
	for(int i=0;i<lim;i++) {
		for(int j=0;j<lim;j++) {
			bs[w[i]+w[w.size()-j-1]]++;
		}
	}
	for(const auto& it: bs) {
		if(it.second >= lim-k) {
			if(test(w,it.first) >= n/2) {
				res = it.first;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++) {
      |              ~^~~~~~~~~

• 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