Submission #26815

#	Time	Username	Problem	Language	Result	Execution time	Memory
26815		szawinis	Watching (JOI13_watching)	C++14	0 / 100	99 ms	2180 KiB

watching

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

int n, p, q;
vector<int> a;
int find_next(int start, int len) {
	int i = start+1;
	while(a[i] - a[start] + 1 <= len && i < n) i++;
	return i;
}
int calc_p(int start, int len) {
	int ret = 0;
	for(int i = start; i < n; i = find_next(i, len)) ret++;
	return ret;
}
bool check(int len) {
	int cntp = 0, cntq = 0;
	for(int i = 0; i < n; i++) {
		if(cntq < q) {
			int j1 = find_next(i, len);
			int j2 = find_next(i, 2*len);
			if(calc_p(j2, len) < calc_p(j1, len)) cntq++, i = j2-1;
			else cntp++, i = j1-1;
		} else {
			cntp++;
			i = find_next(i, len)-1;
		}
	}
	return cntp - p <= q - cntq;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> p >> q;
	a.resize(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	int l = 1, r = 1e9;
	while(l < r) {
		int mid = l+r >> 1;
		if(check(mid)) r = mid;
		else l = mid+1;
	}
	cout << l;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:40:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l+r >> 1;
              ^

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