Submission #370989

#	Time	Username	Problem	Language	Result	Execution time	Memory
370989		shivensinha4	Robots (IOI13_robots)	C++17	100 / 100	2794 ms	23560 KiB

robots

#include "bits/stdc++.h"
#include"robots.h"
#ifdef mlocal
#include "grader.c"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#define endl '\n'

int a, b, t;
vi wlim, slim;
vector<ii> toys;

bool check(ll box) {
	vector<bool> done(t);
	vi ct(b, box);
	int pt = 0;
	
	set<ii> s;
	
	for_(i, 0, b) s.insert({slim[i], i});
	
	for_(i, 0, t) {
		auto pt = s.lower_bound({toys[i][1], -1});
		if (pt != s.end()) {
			done[i] = true;
			if (ct[(*pt)[1]] == 1) s.erase(pt);
			else ct[(*pt)[1]] -= 1;
		}
	}
	
	pt = 0;
	for_(i, 0, a) {
		int ct = 0;
		while (pt < t and ct < box) {
			if (!done[pt] and toys[pt][0] <= wlim[i]) {
				ct++;
				done[pt] = true;
			}
			pt++;
		}
	}
	
	for_(i, 0, t) if (!done[i]) return false;
	return true;
}


int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    a = A, b = B, t = T;
	wlim.reserve(A); slim.reserve(B); toys.reserve(T);
    for_(i, 0, a) {
		wlim.push_back(X[i]);
		wlim[i] -= 1;
    }
	for_(i, 0, b) {
		slim.push_back(Y[i]);
		slim[i] -= 1;
    }
	for_(i, 0, t) toys.push_back({W[i], S[i]});
	sort(wlim.begin(), wlim.end(), greater<>());
	sort(slim.begin(), slim.end(), greater<>());
	sort(toys.begin(), toys.end(), greater<>());
	
	for_(i, 0, t) if ((a == 0 or toys[i][0] > wlim[0]) and (b == 0 or toys[i][1] > slim[0])) return -1;
	
	int l = 1, r = T+1, ans = r;
	while (l < r) {
		int mid = (l+r)/2;
		bool fin = check(mid);
		if (fin) {
			ans = r = mid;
		} else l = mid+1;
	}
	
	return ans;
}

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