제출 #197501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197501		handlename	로봇 (IOI13_robots)	C++17	100 / 100	1962 ms	24688 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	sort(X,X+A);
	sort(Y,Y+B);
	if (T<=50){
	    multiset<pair<int,int> > weight;
    	multiset<pair<int,int> > sizee;
    	for (int i=0;i<T;i++){
    	    if (W[i]>=X[A-1] && S[i]>=Y[B-1]) return -1;
    	    weight.insert(make_pair(W[i],S[i]));
    	    sizee.insert(make_pair(S[i],W[i]));
    	}
    	int wstart=0,sstart=0,total=0;
    	while (!weight.empty()){
    	    for (int i=wstart;i<A;i++){
    	        auto it=weight.lower_bound(make_pair(X[i],0));
    	        if (it==weight.begin()){
    	            wstart=i;
    	            continue;
    	        }
    	        else {
    	            it--;
    	            int curw=(*it).first;
    	            int curs=(*it).second;
    	            weight.erase(it);
    	            sizee.erase(sizee.find(make_pair(curs,curw)));
    	        }
    	    }
    	    for (int i=sstart;i<B;i++){
    	        auto it=sizee.lower_bound(make_pair(Y[i],0));
    	        if (it==sizee.begin()){
    	            sstart=i;
    	            continue;
    	        }
    	        else {
    	            it--;
    	            int curs=(*it).first;
    	            int curw=(*it).second;
    	            sizee.erase(it);
    	            weight.erase(weight.find(make_pair(curw,curs)));
    	        }
    	    }
    	    total++;
    	}
    	return total;
	}
	for (int i=0;i<T;i++){
	    if (W[i]>=X[A-1] && S[i]>=Y[B-1]) return -1;
	}
	pair<int,int> toys[T];
	for (int i=0;i<T;i++) toys[i]=make_pair(W[i],S[i]);
	sort(toys,toys+T);
	int mini=0,maxi=T;
	while (mini+1<maxi){
	    int mid=(mini+maxi)/2;
	    priority_queue<int> pq; //stores sizes
	    int id=0;
	    for (int i=0;i<A;i++){
	        while (id<T && toys[id].first<X[i]){
	            pq.push(toys[id].second);
                id++;
	        }
	        int countt=0;
	        while (!pq.empty() && countt<mid){
	            pq.pop();
	            countt++;
	        }
	    }
        for (int i=id;i<T;i++) pq.push(toys[id].second);
	    for (int i=B-1;i>=0;i--){
	        int countt=0;
	        while ((!pq.empty() && pq.top()<Y[i]) && countt<mid){
	            pq.pop();
	            countt++;
	        }
	    }
	    if (pq.empty()) maxi=mid;
	    else mini=mid;
	}
	return maxi;
}

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