제출 #1310447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310447		am_aadvik	로봇 (IOI13_robots)	C++20	90 / 100	3094 ms	35912 KiB

robots

#ifndef __ROBOTS_H__
#define __ROBOTS_H__

#ifdef __cplusplus
extern "C" {
#endif

	int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]);

#ifdef __cplusplus
}
#endif

#endif /* __ROBOTS_H__ */

#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
const int inf = 2e9 + 5;
#define SUBMIT 1
using namespace std;

///////////////////////////////////////////////////////////////////////////
//main code starts

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	vector<int> x(A), y(B), w(T), sz(T);
	vector<pair<int, int>> swa(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) w[i] = W[i], sz[i] = S[i];
	for (int i = 0; i < T; ++i) swa[i] = { w[i], sz[i] };
	sort(x.begin(), x.end()); sort(y.begin(), y.end());
	sort(swa.begin(), swa.end()); ;
	x.push_back(inf);

	int s = 1, e = T, ans = -1;
	while (s <= e) {
		int t = (s + e) / 2;
		if (!B) {
			int cur = 0, j = 0;
			for (int i = 0; i <= A; ++i) {
				while ((j < T) && (swa[j].first < x[i]))
					++cur, ++j;
				if (x[i] == inf) continue;
				int op = t;
				while ((op--) && cur) --cur;
			}
			if (!cur) ans = t, e = t - 1;
			else s = t + 1;
			continue;
		}
		multiset<int> cur;
		int j = 0;
		for (int i = 0; i <= A; ++i) {
			while ((j < T) && (swa[j].first < x[i]))
				cur.insert(swa[j].second),
				++j;
			if (x[i] == inf) continue;
			if (cur.empty()) continue;
			auto it = prev(cur.end()); int op = t;
			while ((op--) && !cur.empty()) {
				if (it != cur.begin())
					--it,
					cur.erase(next(it));
				else {
					cur.erase(it);
					break;
				}
			}
		}
		if (cur.size()) {
			auto it = prev(cur.end());
			for (int i = B - 1; i >= 0; --i) {
				if (cur.empty()) continue;
				auto it = prev(cur.end()); int op = t;
				while ((op--) && !cur.empty()) {
					if ((*it) >= y[i]) break;
					if (it != cur.begin())
						--it,
						cur.erase(next(it));
					else {
						cur.erase(it);
						break;
					}
				}
			}
		}
		bool ok = cur.empty();
		if (ok) ans = t, e = t - 1;
		else s = t + 1;
	}
	return ans;
}
///////////////////////////////////////////////////////////////////////////

#ifndef SUBMIT
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int a, b, t; cin >> a >> b >> t;
	int x[1000], y[1000], w[1000], s[1000];
	for (int i = 0; i < a; ++i)  cin >> x[i];
	for (int i = 0; i < b; ++i) cin >> y[i];
	for (int i = 0; i < t; ++i) cin >> w[i] >> s[i];
	cout << putaway(a, b, t, x, y, w, s);
}
#endif

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