oj.uz

Submission #1106438

# Submission time Handle Problem Language Result Execution time Memory
1106438 2024-10-30T10:43:39 Z xnqs Watching (JOI13_watching) C++17
0 / 100
 1 ms 336 KB 
#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";
	}
	
	// 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";
		}
	}

	// 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";
		}
	}
	
	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

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -