Submission #211697

#	Time	Username	Problem	Language	Result	Execution time	Memory
211697		spdskatr	Robots (IOI13_robots)	C++14	90 / 100	1591 ms	26732 KiB

robots

#include "robots.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstring>
#include <queue>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

int A, B, T, x[50005], y[50005], w[1000005], s[1000005], maxsz, maxwt;
pii byweight[1000005];
priority_queue<int> pq;

int check(int time) {
	while (!pq.empty()) pq.pop();
	// Let weak toys go first
	int ptr = 0;
	for (int i = 0; i < A; i++) {
		while (ptr < T && byweight[ptr].fi < x[i]) {
			pq.push(s[byweight[ptr].se]);
			ptr++;
		}
		for (int j = 0; !pq.empty() && j < time; j++) {
			pq.pop();
		}
	}
	while (ptr < T) {
		pq.push(s[byweight[ptr].se]);
		ptr++;
	}
	for (int i = B-1; i >= 0; i--) {
		if (!pq.empty() && pq.top() >= y[i]) {
			return 0; // Game over
		}
		for (int j = 0; !pq.empty() && j < time; j++) {
			pq.pop();
		}
	}
	if (!pq.empty()) {
		while (!pq.empty()) pq.pop();
		return 0;
	} else {
		return 1;
	}
}

int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[]) {
	A = a, B = b, T = t;
	int cooked = 0;
	for (int i = 0; i < A; i++) {
		x[i] = X[i];
		maxwt = max(maxwt, x[i]);
	}
	for (int i = 0; i < B; i++) {
		y[i] = Y[i];
		maxsz = max(maxsz, y[i]);
	}
	for (int i = 0; i < T; i++) {
		w[i] = W[i], s[i] = S[i];
		byweight[i] = { w[i], i };
		if (s[i] >= maxsz && w[i] >= maxwt) return -1;
	}
	sort(x, x+A);
	sort(y, y+B);
	sort(byweight, byweight+T);
	int lo = 0, hi = 100000;
	while (lo + 1 < hi) {
		int mid = (lo + hi) / 2;
		if (check(mid)) hi = mid;
		else lo = mid;
	}
	return hi;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:52:6: warning: unused variable 'cooked' [-Wunused-variable]
  int cooked = 0;
      ^~~~~~

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