Submission #1106454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106454		xnqs	Watching (JOI13_watching)	C++17	0 / 100	1 ms	504 KiB

watching

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
 
int x, p, q;
std::vector<int> arr;
 
bool can_solve(int cap, bool debug = 0) {
	std::vector<int> tmp = arr;
	if (debug) {
		for (const auto& i : tmp) {
			std::cout << i << " ";
		}
		std::cout << "\n";
	}
  
  // then the small cameras
	for (int iterations = 0; iterations < p && !tmp.empty(); iterations++) {
		int w = cap;
		int max = -1, max_l = -1, max_r = -1;
		for (int l = 0, r = 0; r < tmp.size(); r++) {
			while (tmp[r]-tmp[l]+1 > w) {
				++l;
			}
 
			if (r-l+1>max) {
				max = r-l+1;
				max_l = l;
				max_r = r;
			}
		}
 
		tmp.erase(tmp.begin()+max_l,tmp.begin()+max_r+1);
		if (debug) {
			std::cout << max_l << " " << max_r << "\n";
			for (const auto& i : tmp) {
				std::cout << i << " ";
			}
			std::cout << "\n";
		}
	}
	
	// first use the large cameras
	for (int iterations = 0; iterations < q && !tmp.empty(); iterations++) {
		int w = 2*cap;
		int max = -1, max_l = -1, max_r = -1;
		for (int l = 0, r = 0; r < tmp.size(); r++) {
			while (tmp[r]-tmp[l]+1 > w) {
				++l;
			}
 
			if (r-l+1>max) {
				max = r-l+1;
				max_l = l;
				max_r = r;
			}
		}
 
		tmp.erase(tmp.begin()+max_l,tmp.begin()+max_r+1);
		if (debug) {
			std::cout << max_l << " " << max_r << "\n";
			for (const auto& i : tmp) {
				std::cout << i << " ";
			}
			std::cout << "\n";
		}
	}
	
	return tmp.empty();
}
 
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
 
	std::cin >> x >> p >> q;
 
	// we only need at most x cameras in total, out of which we'll greedily take as many big cameras as possible
	if (p+q>x) {
		q = std::min(q, x);
		p = x-q;
	}
 
	for (int i = 0, tmp; i < x; i++) {
		std::cin >> tmp;
		arr.emplace_back(tmp);
	}
 
	std::sort(arr.begin(),arr.end());
	const auto bs = [&]() {
		int ret = 1000000001;
		int l = 1, r = 1000000000;
		while (l<=r) {
			int m = (l+r)>>1;
			if (can_solve(m)) {
				ret = m;
				r = m-1;
			}
			else {
				l = m+1;
			}
		}
		return ret;
	};
 
	std::cout << bs() << "\n";
	//can_solve(bs(),1);
}

Compilation message (stderr)

watching.cpp: In function 'bool can_solve(int, bool)':
watching.cpp:24:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for (int l = 0, r = 0; r < tmp.size(); r++) {
      |                          ~~^~~~~~~~~~~~
watching.cpp:50:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for (int l = 0, r = 0; r < tmp.size(); r++) {
      |                          ~~^~~~~~~~~~~~

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