Submission #1192468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192468		lance0	Robots (IOI13_robots)	C++20	90 / 100	3093 ms	12652 KiB

robots

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

int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[]) {
	vector<int> x,y;
	int rob_w_max = 0, rob_s_max = 0;
	for (int i = 0; i < A; i++) {
		x.push_back(X[i]);
		rob_w_max = max(rob_w_max, X[i]);
	}
	for (int i = 0; i < B; i++) {
		y.push_back(Y[i]);
		rob_s_max = max(rob_s_max, Y[i]);
	}
	//note: weakest robots should take as much as possible first since size will never affect them
	sort(x.begin(),x.end());
	//but largest robots should take as much as possible to ensure smaller robots have something to grab
	sort(y.begin(),y.end(), greater<int>());
	int w_max = 0, s_max = 0;
	//combine weight/size requirements into one array for sorting
	vector<pair<int,int>> ws;
	bool flag = true;
	for (int i = 0; i < T; i++) {
		if (flag == false) {
			break;
		}
		if (A > 0 and B > 0) {
			if (W[i] >= x[A-1] and S[i] >= y[0]) {
				flag = false;
			}
		} else if (A > 0) {
			if (W[i] >= x[A-1]) {
				flag = false;
			}
		} else {
			if (S[i] >= y[0]) {
				flag = false;
			}
		}
		ws.push_back(make_pair(W[i],S[i]));
	}
	sort(ws.begin(),ws.end());
	//cleaner to do it now than worry about it in binsearch, though slower
	if (flag == false) {
		return -1;
	} else {
		int low = 0, high = T;
		while(low < high) {
			int mid = (low + high) / 2;
			priority_queue<int> pq;
			int count = 0; // counting toys doable by weak
			for (int i = 0; i < A; i++) {
				while (count < T) {
					if (ws[count].first < x[i]) {
						pq.push(ws[count].second);
						count++;
					} else {
						break;
					}
				}
				for (int j = 0; j < mid; j++) {
					if (!pq.empty()) {
						pq.pop();
					} else {
						break;
					}
				}
			}
			for (int i = count; i < T; i++) {
				pq.push(ws[i].second);
			}
			for (int i = 0; i < B; i++) {
				if (pq.size() == 0) {
					break;
				} else {
					for (int j = 0; j < mid; j++) {
						if (!pq.empty()) {
							if (pq.top() < y[i]) {
								pq.pop();
							}
						} else {
							break;
						}
					}
				}
			}
			if (pq.size() > 0) {
				low = mid + 1;
			} else {
				high = mid;
			}
		}
		return low;
	}
	return 0;
}

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