Submission #39327

#	Time	Username	Problem	Language	Result	Execution time	Memory
39327		14kg	Robots (IOI13_robots)	C++11	100 / 100	2209 ms	22492 KiB

robots

#include "robots.h"
#include <algorithm>
#include <queue>
#include <functional>
#define N 1000001
#define max2(x,y) (x>y?x:y)

using namespace std;
int len_a, len_b, len_toy, pass_len;
int A[50001], B[500010], pass[N];
pair<int, int> toy[N];
priority_queue<int,vector<int>,greater<int> > Q;

bool Can(int max_size) {
	int k = len_a;
	long long r_size = 0;
	
	pass_len = 0;
	while (!Q.empty()) Q.pop();
	for (int i = len_toy; i >= 1; i--) {
		while (toy[i].first <= A[k]) k--, r_size += (long long)max_size;

		r_size--, Q.push(toy[i].second);
		if (r_size < 0) pass[++pass_len] = Q.top(), Q.pop(), r_size++;
	}

	sort(pass + 1, pass + pass_len + 1); 
	k = len_b + 1, r_size = 0;
	for (int i = pass_len; i >= 1; i--) {
		if (!r_size) k--, r_size = (long long)max_size;
		if (!k) return false;
		if (pass[i] > B[k]) return false;
		r_size--;
	}
	return true;
}

int putaway(int _la, int _lb, int _lt, int _A[], int _B[], int in1[], int in2[]) {
	int A_MAX = 0, B_MAX = 0;
	
	len_a = _la, len_b = _lb, len_toy = _lt;
	for (int i = 0; i < len_a; i++) A[i + 1] = _A[i] - 1, A_MAX = max2(A_MAX, _A[i] - 1);
	for (int i = 0; i < len_b; i++) B[i + 1] = _B[i] - 1, B_MAX = max2(B_MAX, _B[i] - 1);
	for (int i = 0; i < len_toy; i++) {
		toy[i + 1] = { in1[i],in2[i] };
		if (in1[i] > A_MAX && in2[i] > B_MAX) return -1;
	}
	sort(toy + 1, toy + len_toy + 1);
	sort(A + 1, A + len_a + 1), sort(B + 1, B + len_b + 1);

	int l = 1, r = len_toy, mid;
	while (l <= r) {
		mid = (l + r) / 2;
		if (Can(mid)) r = mid - 1;
		else l = mid + 1;
	}

	return r + 1;
}

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