제출 #59144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59144		aome	Robots (IOI13_robots)	C++17	0 / 100	4 ms	1292 KiB

robots

#include "robots.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 1000005;
const int M = 50005;

int A, B, T;
int X[M], Y[M];
pair<int, int> a[N];

bool check(int x) {
	int ptr = 0;
	priority_queue<int> pq;
	for (int i = 0; i < A; ++i) {
		while (ptr < T && a[ptr].first < X[i]) pq.push(a[ptr++].second);
		int cur = x;
		while (cur && pq.size()) pq.pop(), cur--;
	}
	while (ptr < T) pq.push(a[ptr++].second);
	for (int i = B - 1; i >= 0; --i) {
		int cur = x;
		while (cur && pq.size() && pq.top() < Y[i]) pq.pop(), cur--;
	}
	return pq.size() == 0;
}

int putaway(int _A, int _B, int _T, int _X[], int _Y[], int W[], int S[]) {
	A = _A, B = _B, T = _T;
	for (int i = 0; i < A; ++i) {
		X[i] = _X[i];
	}
	for (int i = 0; i < B; ++i) {
		Y[i] = _Y[i];
	}
	for (int i = 0; i < T; ++i) {
		a[i] = {W[i], S[i]};
	}
	sort(W, W + A);
	sort(S, S + B);
	sort(a, a + T);
	int l = 1, r = T;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid; else l = mid + 1;
	}
	if (!check(l)) return -1;
	return l;
}

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