Submission #423658

#	Time	Username	Problem	Language	Result	Execution time	Memory
423658		errorgorn	Table Tennis (info1cup20_tabletennis)	C++17	100 / 100	2649 ms	398508 KiB

tabletennis

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back

#define rep(x,s,e) for (auto x=s;x!=e;x++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,k;
int arr[160005];
ll cnt[34000005];
int ba[34000005];

uint __hash(int x){
	x^=(x<<17);
	x^=(x>>13);
	x^=(x<<6);
	return x;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	rep(x,0,n+k) cin>>arr[x];
	
	int l=n,r=n+k+k;
	rep(x,0,n+k){
		l--,r--;
		
		if (r<x) break;
		
		int a=max(x+1,l),b=min(r,n+k)+1;
		rep(y,a,b){
			int hh=__hash(arr[x]+arr[y])&33554431;
			cnt[hh]++;
			ba[hh]=arr[x]+arr[y];
		}
	}
	
	int val;
	
	rep(x,0,33554432) if (cnt[x]>=n/2){
		val=ba[x];
		break;
	}
	
	vector<int> ans;
	
	r=n+k-1;
	rep(x,0,n+k){
		while (arr[x]+arr[r]>val) r--;
		if (arr[x]+arr[r]==val){
			ans.pub(arr[x]);
			ans.pub(arr[r]);
			r--;
			
			if (sz(ans)==n) break;
		}
	}
	
	sort(all(ans));
	
	for (auto &it:ans) cout<<it<<" "; cout<<endl;
}

Compilation message (stderr)

tabletennis.cpp: In function 'int main()':
tabletennis.cpp:78:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   78 |  for (auto &it:ans) cout<<it<<" "; cout<<endl;
      |  ^~~
tabletennis.cpp:78:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   78 |  for (auto &it:ans) cout<<it<<" "; cout<<endl;
      |                                    ^~~~
tabletennis.cpp:66:23: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |   while (arr[x]+arr[r]>val) r--;
      |          ~~~~~~~~~~~~~^~~~

• 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