oj.uz

Submission #26815

# Submission time Handle Problem Language Result Execution time Memory
26815 2017-07-06T07:05:31 Z szawinis Watching (JOI13_watching) C++14
0 / 100
 99 ms 2180 KB 
#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

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.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2180 KB Output is correct
2 Correct 0 ms 2180 KB Output is correct
3 Correct 99 ms 2180 KB Output is correct
4 Correct 86 ms 2180 KB Output is correct
5 Correct 89 ms 2180 KB Output is correct
6 Correct 96 ms 2180 KB Output is correct
7 Correct 0 ms 2180 KB Output is correct
8 Incorrect 59 ms 2180 KB Output isn't correct
9 Halted 0 ms 0 KB -