Submission #272188

#	Time	Username	Problem	Language	Result	Execution time	Memory
272188		Berted	Robots (IOI13_robots)	C++14	90 / 100	3075 ms	33376 KiB

robots

#include "robots.h"
#include <algorithm>
#include <queue>
#include <iostream>
#define pii pair<int, int>
#define fst first
#define snd second
#define ppi pair<pii, int>
using namespace std;

const int INF = 1e9;

int N, M, K, a[50001], b[50001];
pii ar[1000001], srt[1000001];
bool used[1000001];

inline int eval(int k)
{
	priority_queue<pii> pq;
	//cout << "Evaluating : " << k << "\n";
	for (int i = 0; i < K; i++) {used[i] = 0;}
	int j = 0;
	for (int i = 0; i < M; i++)
	{
		for (; j < K && srt[j].fst < b[i]; j++) {pq.push({ar[srt[j].snd].fst, srt[j].snd});}
		for (int j = 0; j < k && pq.size(); j++) {used[pq.top().snd] = 1; pq.pop();}
	}
	while (pq.size()) pq.pop();

	j = N - 1;
	for (int i = K - 1; i >= 0; i--)
	{
		if (!used[i])
		{
			for (; j >= 0 && a[j] > ar[i].fst; j--) {pq.push({0, j});}
			if (pq.size()) {int u = pq.top().fst, v = pq.top().snd; pq.pop(); pq.push({u - 1, v});}
			else {return INF;}
		}
	}
	int ret = 0;
	while (pq.size()) {ret = -pq.top().fst; pq.pop();}
	return ret;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) 
{
	//cout << "Test\n";
	N = A; M = B; K = T;
	for (int i = 0; i < N; i++) {a[i] = X[i];}
	for (int i = 0; i < M; i++) {b[i] = Y[i];}
	for (int i = 0; i < K; i++) {ar[i] = {W[i], S[i]};}
	//cout << "Test\n";
	sort(a, a + N); sort(b, b + M); sort(ar, ar + K);
	
	for (int i = 0; i < K; i++) {srt[i] = {ar[i].snd, i};}
	sort(srt, srt + K);
	
	//cout << "Test\n";

	int L = 0, R = T + 1;
	while (L < R)
	{
		int M = L + R >> 1;
		//cout << L << " " << R << "\n";
		if (eval(M) > M) L = M + 1;
		else R = M;
	}
	int res = INF;
	for (int i = max(0, L - 2); i <= min(T + 1, L + 1); i++)
	{
		res = min(res, max(eval(i), i));
	}
	if (res == INF) return -1;
	else return res;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:63:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |   int M = L + R >> 1;
      |           ~~^~~

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