Submission #391764

#	Time	Username	Problem	Language	Result	Execution time	Memory
391764		ritul_kr_singh	Robots (IOI13_robots)	C++17	100 / 100	2150 ms	28320 KiB

robots

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sp << ' ' <<
#define nl << '\n'
#include "robots.h"

int putaway(int a, int b, int n, int x[], int y[], int wt[], int sz[]){
	sort(x, x+a);
	sort(y, y+b);

	array<int, 2> byWt[n];
	for(int i=0; i<n; ++i) byWt[i] = {wt[i], i};
	sort(byWt, byWt+n);

	int low = 0, high = n+1;
	while(low < high){
		int lim = (low+high) / 2;

		int p = 0;
		priority_queue<pair<int, int>> q;

		for(int i=0; i<a; ++i){
			while(p < n and byWt[p][0] < x[i]){
				q.emplace(sz[byWt[p][1]], byWt[p][1]);
				++p;
			}
			int left = lim;
			while(left and !q.empty()) q.pop(), --left;
		}

		while(p < n){
			q.emplace(sz[byWt[p][1]], byWt[p][1]);
			++p;
		}

		for(int i=b-1; i>=0; --i){
			int left = lim;
			while(left and !q.empty() and q.top().first < y[i]) q.pop(), --left;
		}

		if(!q.empty()) low = lim+1;
		else high = lim;
	}
	if(low > n) low = -1;
	return low;
}

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