Submission #1192455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192455		lance0	Robots (IOI13_robots)	C++20	0 / 100	349 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;
	for (int i = 0; i < T; i++) {
		w_max = max(w_max, W[i]);
		s_max = max(s_max, S[i]);
		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 (w_max > rob_w_max and s_max > rob_s_max) {
		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[i].first < x[i]) {
						pq.push(ws[i].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;
	}
}

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