Submission #720702

#	Time	Username	Problem	Language	Result	Execution time	Memory
720702		PenguinsAreCute	Robots (IOI13_robots)	C++17	100 / 100	940 ms	29080 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef vector<int> vi;
#define REP(i, a, b) for(int i = a; i < b; i++)
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	sort(X, X + A);
	sort(Y, Y + B);
	vi wV[A + 1], sV[B + 1];
	REP(i, 0, T) {
		W[i] = upper_bound(X, X + A, W[i]) - X;
		wV[W[i]].pb(i);
	}
	REP(i, 0, T) {
		S[i] = upper_bound(Y, Y + B, S[i]) - Y;
		sV[S[i]].pb(i);
	}
	int l = 0, h = T + 1;
	while(h - l > 1) {
		int mid = (l + h) / 2;
		priority_queue<int> pq;
		REP(i, 0, A) {
			for(auto j: wV[i]) pq.push(S[j]);
			for(int j = 0; j < mid && !pq.empty(); j++) pq.pop();
		}
		for(auto i: wV[A]) pq.push(S[i]);
		bool ok = true;
		for(int i = 0; !pq.empty(); i++) {
			if(!pq.empty() && pq.top() >= B - i) {
				ok = false; break;
			}
			for(int j = 0; j < mid && !pq.empty(); j++) pq.pop();
		}
		if(ok) h = mid;
		else l = mid;
	}
	if(h == T + 1) return -1;
	return h;
}

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