Submission #990458

#	Time	Username	Problem	Language	Result	Execution time	Memory
990458		aaaaaarroz	Robots (IOI13_robots)	C++17	100 / 100	1313 ms	14272 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	vector<int> x(A);
	for(int i=0;i<A;i++){
		x[i]=X[i];
	}
	sort(all(x));
	vector<int> y(B);
	for(int i=0;i<B;i++){
		y[i]=Y[i];
	}
	sort(all(y));
	vector<pair<int,int>> toy(T);
	for(int i=0;i<T;i++){
		toy[i]={W[i],S[i]};
	}
	sort(all(toy));
	int ng=0,ok=T+1;
	while(ok-ng>1){
		int mid=(ok+ng)/2;
		int cnt=0;
		priority_queue<int,vector<int>,less<int>> pq1; 
		for(int i=0;i<A;i++){
			while(cnt<T&&toy[cnt].first<x[i]){
				pq1.push(toy[cnt].second);
				cnt++;
			}
			for(int j=0;j<mid;j++){
				if(pq1.empty())break;
				pq1.pop();
			}
		}
		priority_queue<int,vector<int>,greater<int>> pq2;
		while(cnt<T){
			pq2.push(toy[cnt].second);
			cnt++;
		}
		while(!pq1.empty()){
			pq2.push(pq1.top());
			pq1.pop();
		}
		for(int i=0;i<B;i++){
			for(int j=0;j<mid;j++){
				if(pq2.empty())break;
				if(pq2.top()>=y[i])break;
				pq2.pop();
			}
		}
		if(pq2.empty())ok=mid;
		else ng=mid;
	}
	if(ok==T+1)return -1;
	return ok;
}

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