Submission #405138

#	Time	Username	Problem	Language	Result	Execution time	Memory
405138		Aryan_Raina	Robots (IOI13_robots)	C++14	100 / 100	1784 ms	24276 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

#define ar array
const int INF = 1e9+9;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	ar<int,2> toy[T];
	for (int i = 0; i < T; i++) toy[i] = {W[i], S[i]};

	sort(toy, toy + T); sort(X, X + A); sort(Y, Y + B);

	auto check = [&](int remdi) {
		priority_queue<int> pq;

		// choose as many toys u can with max S, and move out with X
		int j = 0;
		for (int i = 0; i < A; i++) {
			for (; j < T && toy[j][0] < X[i]; j++) pq.push(toy[j][1]);
			for (int r = 0; r < remdi && !pq.empty(); r++) pq.pop();
		}

		// add in remaining toys
		for (; j < T; j++) pq.push(toy[j][1]);

		// use Y bots to move out
		for (int i = B - 1; i >= 0; i--)
			for (int r = 0; r < remdi && !pq.empty() && pq.top() < Y[i]; r++) 
				pq.pop();

		return pq.empty();
	};

	int ans = INF, lo = 0, hi = T, mid;
	while (lo <= hi) {
		mid = (lo + hi) >> 1;
		if (check(mid)) hi = mid - 1, ans = mid;
		else lo = mid + 1;
	}

    return ans == INF ? -1 : ans;
}

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