Submission #746233

#	Time	Username	Problem	Language	Result	Execution time	Memory
746233		Abrar_Al_Samit	Table Tennis (info1cup20_tabletennis)	C++17	24 / 100	1168 ms	5480 KiB

tabletennis

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

const int nax = 150403;

int n, k;
int a[nax];
int at;
int pre[nax], premx[nax], suf[nax];
int solve(int gap) {
	for(int i=0; i<nax; ++i) {
		pre[i] = premx[i] = suf[i] = 0;
	}

	int ptr = 1;
	for(int i=1; i<=n+k; ++i) {
		while(ptr+1<i && a[i]-a[ptr+1]>=gap) ++ptr;


		pre[i] = 1;
		if(a[i]-a[ptr]==gap) {
			pre[i] = 1 + pre[ptr];
		}
		premx[i] = max(pre[i], premx[i-1]);
	}

	int best = 0;
	ptr = n+k;
	for(int i=n+k; i>0; --i) {
		while(ptr-1>i && a[ptr-1]-a[i]>=gap) --ptr;

		suf[i] = 1;
		if(a[ptr]-a[i]==gap) {
			suf[i] = 1 + suf[ptr];
		}

		if(best < min(premx[i-1], suf[i])) {
			best = min(premx[i-1], suf[i]);
			at = i;
		}
	}

	return best;
}
void PlayGround() {
	cin>>n>>k;
	for(int i=1; i<=n+k; ++i) {
		cin>>a[i];
	}

	int best_gap;
	int best = 0;
	for(int i=2; i<=min(n+k, 2*k+2); ++i) {
		int cur = solve(a[i]-a[i-1]);
		if(best < cur) {
			best = cur;
			best_gap = a[i] - a[i-1];
		}
	}
	assert(solve(best_gap)>=n/2);

	vector<int>right_wing = {a[at]};
	int j = at+1;
	int prv = at;
	while(j<=n+k) {
		if(a[j]-a[prv]>best_gap) break;
		if(a[j]-a[prv]<best_gap) ++j;
		else {
			right_wing.push_back(a[j]);
			prv = j;
			++j;
		}
	}

	j = at-1;
	while(j>0) {
		if(min(pre[j], (int)right_wing.size()) * 2 >= n) break;
		--j;
	}
	at = j;

	vector<int>left_wing = {a[at]};
	j = at-1;
	prv = at;
	while(j>0) {
		if(a[prv]-a[j]>best_gap) break;
		if(a[prv]-a[j]<best_gap) --j;
		else {
			left_wing.push_back(a[j]);
			prv = j;
			--j;
		}
	}

	while(left_wing.size()>right_wing.size()) {
		left_wing.pop_back();
	}
	while(right_wing.size()>left_wing.size()) {
		right_wing.pop_back();
	}
	while(left_wing.size()+right_wing.size()>n) {
		left_wing.pop_back();	
		right_wing.pop_back();
	}

	reverse(left_wing.begin(), left_wing.end());

	for(int x : left_wing) {
		cout<<x<<' ';
	}
	for(int x : right_wing) {
		cout<<x<<' ';
	}


	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

Compilation message (stderr)

tabletennis.cpp: In function 'void PlayGround()':
tabletennis.cpp:101:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |  while(left_wing.size()+right_wing.size()>n) {
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
tabletennis.cpp:87:3: warning: 'best_gap' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |   if(a[prv]-a[j]<best_gap) --j;
      |   ^~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 15 / 15
• Subtask 5: 9 / 9
• Subtask 6: 0 / 14
• Subtask 7: 0 / 15
• Subtask 8: 0 / 13