제출 #309855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
309855		tengiz05	로봇 (IOI13_robots)	C++17	100 / 100	2184 ms	65536 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++;
	//	cout << level << ' ';
	//	cout << wtoys.size() << '\n';
		vector<pair<int, int>> black_list;
		for(auto robot : robots){
		//	auto robot = *r;
			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.push_back(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.push_back(robot);continue;}it--;
				int f = (*it).first;
				int s = (*it).second;
				stoys.erase(stoys.find({f, s}));
				wtoys.erase(wtoys.find({s, f}));
			}//cout << st << ' ';
		}
		for(auto x : black_list){
			robots.erase(robots.find(x));
		}
	}/*for(auto X : wtoys){
		cout << X.first << ' ' << X.second << '\n';
	}*/
	return level;
}

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