oj.uz

Submission #571834

# Submission time Handle Problem Language Result Execution time Memory
571834 2022-06-02T20:45:28 Z 1ne Watching (JOI13_watching) C++14
0 / 100
 4 ms 340 KB 
#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,p,q;cin>>n>>p>>q;
	vector<int>arr(n);
	for (int i = 0;i<n;++i)cin>>arr[i];
	sort(arr.begin(),arr.end());
	int left = 1,right = 1e9;
	int ans = right;
	function<bool(int)>check = [&](int u){
		int cur = 0;
		int sum = arr[0];
		int big = q,small = p;
		while(cur < n){
			int nxt = lower_bound(arr.begin(),arr.end(),sum + 2 * u - 1) - arr.begin();
			int 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)  >= 2 * (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 && big){
				--big;
				cur = nxt + 1;
				sum = arr[cur];
			}
			else if (small){
				cur = cur + 1;
				small--;
				sum = arr[cur];
			}
			else if (big){
				cur = cur + 1;
				big--;
				sum = arr[cur];
			}
			else break;
		}
		return (cur >= n);
	};
	while(left<=right){
		int 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Incorrect 1 ms 328 KB Output isn't correct
8 Halted 0 ms 0 KB -