Submission #93835

#	Time	Username	Problem	Language	Result	Execution time	Memory
93835		vamaddur	Robots (IOI13_robots)	C++14	100 / 100	1688 ms	24480 KiB

robots

/*
Solution
*/

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

using namespace std;

#define PI atan2(0, -1)
#define epsilon 1e-9
#define INF 5000000000000000000
#define MOD 1000000007

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
	sort(X, X+A); sort(Y, Y+B);
	vector<pair<int, int>> toys;
	for(int i = 0; i < T; i++) toys.pb(mp(W[i], S[i]));
	sort(toys.begin(), toys.end());
	int lo = 1, hi = T, ret = -1;
	while(lo <= hi){
		int mid = (lo+hi)/2, idx = 0;
		priority_queue<int> pq;
		for(int i = 0; i < A; i++){
			while(idx < T && X[i] > toys[idx].f) pq.push(toys[idx++].s);
			for(int j = 0; j < mid && pq.size() > 0; j++) pq.pop();
		}
		for(int i = idx; i < T; i++) pq.push(toys[i].s);
		for(int i = B-1; i > -1; i--)
			for(int j = 0; j < mid && pq.size() > 0; j++){
				if(Y[i] > pq.top()) pq.pop();
				else break;
			}
		if(pq.size() == 0){ hi = mid-1; ret = mid; }
		else lo = mid+1;
	}
	return ret;
}

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