Submission #309966

#	Time	Username	Problem	Language	Result	Execution time	Memory
309966		tengiz05	Robots (IOI13_robots)	C++17	100 / 100	2340 ms	61048 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
const int inf = 2e9+7;
using namespace std;
int putaway(int n, int m, int t, int a[], int b[], int w[], int s[]) {
	int mxa = 0, mxb = 0;
	for(int i=0;i<n;i++)mxa = max(mxa, a[i]);
	for(int i=0;i<m;i++)mxb = max(mxb, b[i]);
	for(int i=0;i<t;i++){
		if(mxa <= w[i] && mxb <= s[i])return -1;
	}
	multiset<pair<int, int>> wtoys;
	multiset<pair<int, int>> stoys;
	
	//  weak_toys[i] = {weight, size}
	// small_toys[i] = {size, weight}
	for(int i=0;i<t;i++){
		wtoys.insert({w[i], s[i]});
		stoys.insert({s[i], w[i]});
	}
	multiset<pair<int, int>> robots;
	for(int i=0;i<n;i++){
		robots.insert({a[i], 0});
	}for(int i=0;i<m;i++){
		robots.insert({b[i], 1});
	}
	int level = 0;
	while(wtoys.size()){
		level++;
		set<pair<int, int>> black_list;
		for(auto robot : robots){
			if(!wtoys.size())break;
			int st = robot.first;
			if(robot.second == 0){
				auto it = wtoys.upper_bound({st, -inf});
				if(it == wtoys.begin()){black_list.insert(robot);continue;}it--;
				int f = (*it).first;
				int s = (*it).second;
				wtoys.erase(wtoys.find({f, s}));
				stoys.erase(stoys.find({s, f}));
			}else {
				auto it = stoys.upper_bound({st, -inf});
				if(it == stoys.begin()){black_list.insert(robot);continue;}it--;
				int f = (*it).first;
				int s = (*it).second;
				stoys.erase(stoys.find({f, s}));
				wtoys.erase(wtoys.find({s, f}));
			}
		}
		for(auto x : black_list){
			robots.erase(x);
		}
	}
	return level;
}

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