Submission #540544

#	Time	Username	Problem	Language	Result	Execution time	Memory
540544		sliviu	Robots (IOI13_robots)	C++17	100 / 100	1866 ms	33792 KiB

robots

#include <robots.h>
#include <bits/stdc++.h>

using namespace std;
using pi = pair<int, int>;

int putaway(int A, int B, int T, int* X, int* Y, int* W, int* S) {
	sort(X, X + A), sort(Y, Y + B);
	vector<pi> ax, ay;
	for (int i = 0; i < T; ++i)
		ax.emplace_back(W[i], i), ay.emplace_back(S[i], i);
	sort(ax.begin(), ax.end()), sort(ay.begin(), ay.end());
	int left = 1, right = T + 1;
	auto ok = [&](int d) {
		vector<int> seen(T);
		priority_queue<pi> PQ;
		for (int i = 0, j = 0; i < A; ++i) {
			while (j < T && ax[j].first < X[i])
				PQ.emplace(S[ax[j].second], ax[j].second), ++j;
			for (int k = 0; k < d && !PQ.empty(); ++k, PQ.pop())
				seen[PQ.top().second] = 1;
		}
		queue<int> Q;
		for (int i = 0, j = 0; i < B; ++i) {
			while (j < T && ay[j].first < Y[i]) {
				if (!seen[ay[j].second])
					Q.emplace(ay[j].second);
				++j;
			}
			for (int k = 0; k < d && !Q.empty(); ++k, Q.pop())
				seen[Q.front()] = 1;
		}
		for (int i = 0; i < T; ++i)
			if (!seen[i])
				return 0;
		return 1;
	};
	while (left < right) {
		int m = (left + right) / 2;
		if (ok(m))
			right = m;
		else
			left = m + 1;
	}
	return (left == T + 1 ? -1 : left);
}

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