Submission #384051

#	Time	Username	Problem	Language	Result	Execution time	Memory
384051		aarr	Robots (IOI13_robots)	C++14	90 / 100	3063 ms	15584 KiB

robots

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

const int N = 1000 * 1000 + 5;

int n, m, p, a[N], b[N];
pair <int, int> c[N];


bool isval(int val) {
	vector <int> vec;
	priority_queue <int> s;
	int t = 0;
	for (int i = 0; i < n; i++) {
		while (t < p && c[t].first < a[i]) {
			s.push(c[t].second);
			t++;
		}
		for (int j = 0; j < val; j++) {
			if (s.size()) {
				s.pop();
			}
			else {
				break;
			}
		}
	}
	while (t < p) {
		s.push(c[t].second);
		t++;
	}
	while (s.size()) {
		vec.push_back(s.top());
		s.pop();
	}
//	cout << "72 " << val << " " << s.size() << endl;
//	for (auto x : s) {
//		cout << "71 " << x << endl;
///	}
	for (int i = 0; i <= m; i++) {
//		cout << "74 " << b[i] << endl;
		for (int j = 0; j < val; j++) {
			if (vec.size()) {
				if (vec.back() < b[i]) {
					vec.pop_back();
				}
			} 
			else {
				return true;
			}
		}
	}
//	cout << "73 " << s.size() << endl;
	if (vec.empty()) {
		return true;
	}
	return false;
}

int putaway(int NN, int M, int P, int A[], int B[], int W[], int S[]) {
//	swap(NN, M);
//	swap(A, B);
//	swap(W, S);
	n = NN, m = M, p = P;
	sort(A, A + n);
	sort(B, B + m);
    int dw = 0, up = N;
    for (int i = 0; i < n; i++) {
    	a[i] = A[i];
	}
	for (int i = 0; i < m; i++) {
		b[i] = B[i];
	}
	for (int i = 0; i < p; i++) {
		c[i] = {W[i], S[i]};
	}
	sort(c, c + p);
    while (up - dw > 1) {
    	int md = (dw + up) / 2;
    	if (isval(md)) {
    		up = md;
		}
		else {
			dw = md;
		}
	}
	if (up == N) {
		return -1;
	}
	return up;
}

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