Submission #1165173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165173		tesseract	Robots (IOI13_robots)	C++20	100 / 100	652 ms	21044 KiB

robots

#include "robots.h"
#include <algorithm>
#include <functional>
#include <ranges>
#include <vector>
#include <cassert>
using namespace std;

/* We order all the robots in a single sequence as follows: All the weak
 * robots in *increasing* order of their weight limits, followed by all
 * the small robots in *decreasing* order of their size limits. This way,
 * for each toy, if one looks at the set of robots which can pick up that
 * toy, it forms a contiguous subinterval of the sequence of all robots.
 *
 * At this point, one can rephrase the problem as follows: You are given T
 * subintervals of [0,N) (where N = A + B). For each such interval, you
 * have to choose an integer point in it as its chosen point. For each i
 * in [0, N), the weight of i is the number of intervals for which it has
 * been chosen. Choose points to minimize the maximum weight of all elements
 * of [0, N). Note that in this formulation we don't reference any of the
 * weight or size limits, and we don't make distinction between weak and
 * small robots.
 */

// Interval of integers [L, U).
struct Interval {
	int L, U;

	inline int length() const { return U-L; }
};

bool possible(const vector<vector<int>> &ends, int limit);

int solveForIntervals(vector<Interval> intervals, int N) {
	// each interval is a subinterval of [0,N).

	// Consider all intervals whose beginning is i. The multiset
	// of all their ends is ends[i].
	vector<vector<int>> ends(N);
	for(Interval ivl : intervals) {
		ends[ivl.L].push_back(ivl.U);
	}

	// answer is the smallest limit for which possible(ends, limit) is true.
	// Invariant: answer is in (L, U].
	// ****NOTE**** Rare use of left-open right-closed intervals!
	int L = 0, U = intervals.size();
	while(U-L > 1) {
		int mid = L + (U-L)/2;
		//ez::println("possible ", mid, " ", foo);
		if(possible(ends, mid)) {
			U = mid;
		} else {
			L = mid;
		}
	}
	return U;
}

vector<int> heapOfEnds; // Min heap, so need to use greater()

bool possible(const vector<vector<int>> &ends, int limit) {
	heapOfEnds.reserve(ends.size());
	heapOfEnds.resize(0);

	for(int b : views::iota(int(0), int(ends.size()))) {
		// Looking at all intervals which begin with b.
		// Their endpoints are ends[b]. We add them all
		// into consideration, and then take away at most
		// limit of them - for these intervals, we choose b
		// as their chosen point.
		for(int end : ends[b]) {
			heapOfEnds.push_back(end);
			push_heap(heapOfEnds.begin(), heapOfEnds.end(), greater());
		}

		for(int i=0; i<limit && !heapOfEnds.empty(); ++i) {
			pop_heap(heapOfEnds.begin(), heapOfEnds.end(), greater());
			if(heapOfEnds.back() <= b) {
				// We have an interval ending at heapOfEnds.back(),
				// but we haven't been able to choose a point in it, and it is
				// too late now, as we are past the end.
				return false;
			}
			heapOfEnds.pop_back();
		}
	}
	return heapOfEnds.empty();
}


/* A: number of weak robots.
 * B: number of small robots.
 * T: number of toys.
 * X: array of length A, weight limits of weak robots.
 * Y: array of length B, size limits of small robots.
 * W: array of length T, weight of each toy.
 * S: array of length T, size of each toy.
 */
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {

	sort(X, X+A, less()); // weak robots in increasing order of weight limits.
	sort(Y, Y+B, greater()); // small robots in decreasing order of size limits.

	vector<Interval> intervals;
	intervals.reserve(T);

	for(int t : views::iota(0,T)) {
		Interval ivl {
			int(upper_bound(X, X+A, W[t], less()) - X),
			int(A + (lower_bound(Y, Y+B, S[t], greater()) - Y))
		};
		assert(ivl.length() >= 0);
		if(ivl.length() == 0) {
			return -1;
		}
		intervals.push_back(ivl);
	}
	return solveForIntervals(intervals, A+B);
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10