Submission #361446

#	Time	Username	Problem	Language	Result	Execution time	Memory
361446		NachoLibre	Robots (IOI13_robots)	C++17	100 / 100	1905 ms	19520 KiB

robots

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

const int N = 1000006;
const int MXX = 2e9;
int ga, gb, gn, *x, *y;
pair<int, int> o[N];

bool C(int z) {
	priority_queue<int> s;
	int ox = 0, az = 0;
	for(int i = 0; i < ga; ++i) {
		while(o[ox].first < x[i]) {
			// cout << "[+] " << o[ox].second << endl;
			s.push(o[ox].second);
			++ox;
		}
		az = z;
		while(s.size() && az) {
			// cout << "[-] " << s.top() << endl;
			s.pop();
			--az;
		}
	}
	for(int i = ox; i < gn; ++i) {
		s.push(o[i].second);
	}
	for(int i = gb - 1; i >= 0; --i) {
		az = z;
		while(s.size() && az) {
			if(s.top() >= y[i]) return 0;
			s.pop();
			--az;
		}
	}
	if(s.size()) return 0;
	return 1;
}

int putaway(int a, int b, int n, int _x[], int _y[], int _w[], int _s[]) {
	ga = a; gb = b; gn = n;
	x = _x; y = _y;
	sort(x, x + a);
	sort(y, y + b);
	for(int i = 0; i < n; ++i) {
		o[i] = {_w[i], _s[i]};
	}
	o[n] = {MXX, 0};
	sort(o, o + n);
	if(!C(n)) return -1;
	int l = 1, r = n;
	while(l < r) {
		int m = (l + r) / 2;
		if(C(m)) {
			r = m;
		} else {
			l = m + 1;
		}
	}
	return l;
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _x[] = {6, 2, 9};
	int _y[] = {4, 7};
	int _w[] = {4, 8, 2, 7, 1, 5, 3, 8, 7, 10};
	int _s[] = {6, 5, 3, 9, 8, 1, 3, 7, 6, 5};
	cout << putaway(3, 2, 10, _x, _y, _w, _s) << endl;
	return 0;
}
#endif

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