제출 #538042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538042		pavement	로봇 (IOI13_robots)	C++17	100 / 100	1906 ms	28024 KiB

robots

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

typedef pair<int, int> ii;

bitset<1000005> yes;
ii M[1000005];

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	sort(X, X + A);
	sort(Y, Y + B);
	for (int i = 0; i < T; i++) M[i] = make_pair(W[i], S[i]);
	sort(M, M + T);
	int lo = 1, hi = T, ans = -1;
	for (int i = 0; i < T; i++)
		tie(W[i], S[i]) = M[i];
	while (lo <= hi) {
		yes.reset();
		priority_queue<ii> pq;
		int mid = (lo + hi) / 2, idx = 0;
		for (int i = 0; i < A; i++) {
			for (; idx < T && W[idx] < X[i]; idx++)
				pq.emplace(S[idx], idx);
			for (int j = 0; j < mid && !pq.empty(); j++) {
				yes[pq.top().second] = 1;
				pq.pop();
			}
		}
		priority_queue<int, vector<int>, greater<int> > pq2;
		for (int i = 0; i < T; i++)
			if (!yes[i])
				pq2.push(S[i]);
		for (int i = 0; i < B; i++)
			for (int j = 0; j < mid && !pq2.empty() && pq2.top() < Y[i]; j++)
				pq2.pop();
		if (pq2.empty()) ans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	return ans;
}

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