Submission #158216

#	Time	Username	Problem	Language	Result	Execution time	Memory
158216		NachoLibre	Robots (IOI13_robots)	C++14	0 / 100	2 ms	504 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;

pair<int, int> a[1000006];
bool bo[1000006];
priority_queue<pair<int, int> > q;
priority_queue<int> pq;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	sort(X, X + A);
	sort(Y, Y + B);
	int l = 1, r = T + 1, m;
	for(int i = 0; i < T; ++i) {
		a[i] = {W[i], i};
	}
	sort(a, a + T);
	while(l < r) {
		m = (l + r) / 2;
		while(q.size()) q.pop();
		for(int i = 0; i < T; ++i) bo[i] = 0;
		int wg = 0;
		for(int i = 0; i < A; ++i) {
			for(int j = wg; j < T; ++j) {
				if(a[j].first >= X[i]) {
					wg = j;
					break;
				}
				q.push({S[a[j].second], a[j].second});
			}
			for(int j = 0; j < m; ++j) {
				if(q.size()) bo[q.top().second] = 1, q.pop();
				else break;
			}
		}
		while(pq.size()) pq.pop();
		for(int i = 0; i < T; ++i) {
			if(!bo[i]) {
				pq.push(S[i]);
			}
		}
		bool gmv = 1;
		for(int i = B - 1; i >= 0 && gmv && pq.size(); --i) {
			for(int j = 0; j < m; ++j) {
				if(pq.empty()) break;
				if(pq.top() >= Y[i]) {
					gmv = 0;
					break;
				} else {
					pq.pop();
				}
			}
		}
		if(gmv) {
			r = m;
		} else {
			l = m + 1;
		}
	}
	if(l == T + 1) return -1;
	return l;
}

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