Submission #571845

#	Time	Username	Problem	Language	Result	Execution time	Memory
571845		1ne	Watching (JOI13_watching)	C++14	0 / 100	1 ms	220 KiB

watching

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n,p,q;cin>>n>>p>>q;
	vector<long long>arr(n);
	for (long long i = 0;i<n;++i)cin>>arr[i];
	sort(arr.begin(),arr.end());
	long long left = 1,right = 1e10;
	if (p + q >=n){
		cout<<1<<'\n';
		return 0;
	}
	long long ans = right;
	function<bool(long long)>check = [&](long long u){
		long long cur = 0;
		long long sum = arr[0];
		long long big = q,small = p;
		while(cur < n){
			long long nxt = lower_bound(arr.begin(),arr.end(),sum + 2 * u - 1) - arr.begin();
			long long nxt2 = lower_bound(arr.begin(),arr.end(),sum + u - 1) - arr.begin();
			while(nxt!=n && arr[nxt] - sum > 2 * u - 1)--nxt;
			while(nxt2!=n && arr[nxt2] - sum > u - 1)--nxt2;
			while(nxt + 1<n && arr[nxt + 1] - sum <=2 * u - 1)++nxt;
			while(nxt2 + 1<n && arr[nxt2 + 1] - sum <=u - 1)++nxt2;
			if (nxt - cur >= 1 && (nxt - cur + 1)  > (nxt2 - cur + 1) && big){
				--big;
				cur = nxt + 1;
				sum = arr[cur];
			}
			else if (nxt2 - cur >= 1 && small){
				--small;
				cur = nxt2 + 1;
				sum = arr[cur];
			}
			else if (nxt - cur >= 1 && (nxt - cur + 1)  >= (nxt2 - cur + 1) && big){
				--big;
				cur = nxt + 1;
				sum = arr[cur];
			}
			else if (small){
				cur = nxt2 + 1;
				small--;
				sum = arr[cur];
			}
			else if (big){
				cur = nxt + 1;
				big--;
				sum = arr[cur];
			}
			else break;
		}
		return (cur >= n);
	};
	while(left<=right){
		long long mid = (left + right)>>1;
		if (check(mid)){
			right = mid - 1;
			ans = mid;
		}
		else{
			left = mid + 1;
		}
	}
	cout<<ans<<'\n';
	return 0;
}
	

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50