Submission #373678

#	Time	Username	Problem	Language	Result	Execution time	Memory
373678		cheissmart	Robots (IOI13_robots)	C++14	100 / 100	1981 ms	22312 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") -> " << #x << " is " << (x) << endl
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
 
const int INF = 1e9 + 7;
 
int putaway(int A, int B, int T, int a[], int b[], int W[], int S[]) {
	sort(a, a + A), sort(b, b + B);
	vi p(T);
	iota(ALL(p), 0);
	sort(ALL(p), [&] (int a, int b) {
		return W[a] < W[b];
	});
	auto ok = [&] (int k) { // each people can kill at msot k things
		priority_queue<int> pq;
		int j = 0;
		for(int i = 0; i < A; i++) {
			while(j < T && W[p[j]] < a[i]) {
				pq.push(S[p[j]]);
				j++;
			}
			for(int j = 0; j < k && pq.size(); j++) {
				pq.pop();
			}
		}
		while(j < T) pq.push(S[p[j++]]);
		for(int i = B - 1; i >= 0; i--) {
			for(int j = 0; j < k && pq.size(); j++) {
				if(pq.top() < b[i]) {
					pq.pop();
				} else {
					return false;
				}
			}
		}
		return pq.empty();
	};
 
	int lb = 1, rb = T;
	while(lb <= rb) {
		int mb = (lb + rb) / 2;
		if(ok(mb)) rb = mb - 1;
		else lb = mb + 1;
	}
	if(lb > T) return -1;
	return lb;
}

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