Submission #1283142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283142		Jawad_Akbar_JJ	Robots (IOI13_robots)	C++20	100 / 100	1684 ms	11328 KiB

robots

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "robots.h"

using namespace std;
int cnt1[50005], cnt2[50005];

bool valid(int T, vector<pair<int,int>> &vc, int A, int X[], int B, int Y[], int tm){
	for (int i=0;i<50005;i++)
		cnt1[i] = cnt2[i] = 0;
	set<pair<int,int>> st;
	for (int i=0;i<B;i++)
		st.insert({Y[i], i});
	for (int i=T-1, lst = A - 1;i>=0;i--){
		auto u = st.upper_bound({vc[i].second + 1, -1});
		if (u == end(st)){
			if (lst < 0 or X[lst] <= vc[i].first)
				return 0;
			cnt1[lst]++;
			if (cnt1[lst] == tm)
				lst--;
		}
		else{
			cnt2[(*u).second]++;
			if (cnt2[(*u).second] == tm)
				st.erase(u);
		}
	}
	return 1;
}

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>> vc;
	for (int i=0;i<T;i++)
		vc.push_back({W[i], S[i]});

	sort(begin(vc), end(vc));

	int l = 0, r = T + 1;
	while (l + 1 < r){
		int mid = (l + r) / 2;
		if (valid(T, vc, A, X, B, Y, mid))
			r = mid;
		else
			l = mid;
	}
	if (r == T + 1)
		r = -1;
	return r;
}

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