Submission #766546

#	Time	Username	Problem	Language	Result	Execution time	Memory
766546		Sohsoh84	Robots (IOI13_robots)	C++17	100 / 100	1338 ms	25288 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define all(x)		(x).begin(),(x).end()
#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MAXN = 1e6 + 10;

int n, m, t;
vector<pll> toys;
vector<int> A, B;

inline bool solve(int k) {
	priority_queue<int> pq;
	int p = 0;
	for (int e : A) {
		while (p < int(toys.size()) && e >= toys[p].X) pq.push(toys[p++].Y);
		int x = k;
		while (x > 0 && !pq.empty()) {
			pq.pop();
			x--;
		}
	}
	
	while (p < int(toys.size())) pq.push(toys[p++].Y);
	vector<int> vec;
	while (!pq.empty()) {
		vec.push_back(pq.top());
		pq.pop();
	}

	reverse(all(vec));
	p = 0;
	for (int e : B) {
		int x = k;
		while (p < int(vec.size()) && e >= vec[p] && x > 0) p++, x--;
	}

	return p >= int(vec.size());
}

int putaway(int A_, int B_, int T_, int X_[], int Y_[], int W_[], int S_[]) {
	n = A_, m = B_, t = T_;
	for (int i = 0; i < n; i++) A.push_back(X_[i] - 1);
	for (int i = 0; i < m; i++) B.push_back(Y_[i] - 1);

	for (int i = 0; i < t; i++)
		toys.push_back({W_[i], S_[i]});

	sort(all(A));
	sort(all(B));
	sort(all(toys));

	int l = 1, r = t + 1;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (solve(mid)) r = mid;
		else l = mid + 1;
	}

	return (l > t ? -1 : l);
}

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