Submission #488605

#	Time	Username	Problem	Language	Result	Execution time	Memory
488605		Pulgster	Robots (IOI13_robots)	C++17	100 / 100	1858 ms	25980 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin((x)), end((x))
#define g(x) "[" << #x << ": " << x << "] "
int putaway(int n, int m, int toys, int a[], int b[], int w[], int sz[]) {
	// n of type a - sz doesnt matter		
	// m of type b - weight doesnt matter
	// cerr<<g(toys);
	sort(a, a+n);
	sort(b, b+m);
	vector<int> idx(toys);
	for(int i=0;i<toys;i++){
		idx[i] = i;
	}
	if(n==m && n ==0){
		return -1;
	}
	
	int lo = 0;
	int hi = toys+1;
	sort(all(idx), [&](int one, int two){
		return w[one] < w[two];
	});
	auto f = [&](int how){
		priority_queue<pair<int, int>> pq;
		// start with a since I care about weight but not abotu size
		int cur = 0;
		for(int i=0;i<n;i++){
			while(cur<toys&&w[idx[cur]] < a[i]){
				pq.push({sz[idx[cur]], w[idx[cur]]});
				cur++;
			}
			int cnt = 0;
			while(cnt < how && !pq.empty()){
				pq.pop();
				cnt++;
			
			}
		}
		vector<int> rems;
		while(!pq.empty()){
			rems.push_back(pq.top().first);
			pq.pop();
		}
		for(int i=cur;i<toys;i++){
			rems.push_back(sz[idx[cur]]);
		}
		sort(all(rems));
		// cerr<<g(how) <<'\n';
		// for(int i=0;i<rems.size();i++){
		// 	cerr<<g(i) << g(rems[i]);
		// }
		// cerr<<'\n';
		for(int i=m-1;i>=0;i--){
			int cnt = 0;
			while(cnt<how&&!rems.empty()&&b[i] > rems.back()){
				cnt++;
				rems.pop_back();
			}
		}
		return rems.empty();
	};
	if(f(toys) == 0){
		return -1;
	}
	while(hi != lo){
		int mid = (hi+lo)/2;
		if(f(mid)){
			hi = mid;
		}  else{
			lo = mid+1;
		}
	}
	return hi;
}

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