제출 #242881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242881		cfalas	로봇 (IOI13_robots)	C++14	100 / 100	2447 ms	37100 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#define MID (l+r)/2
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<ii> vii;
#define mp make_pair
#define F first
#define S second

bool s(iii a, iii b){
	if(a.F.S==b.F.S) return a.F.F>b.F.F;
	return a.F.S<b.F.S;
}



int used[1040000] = {};



int putaway(int A, int B, int n, int X[], int Y[], int W[], int S[]) {
	int l=0, r=n;
	int mm=-1;
	sort(X, X+A);
	sort(Y, Y+B);
	vector<iii> toys_small, toys_light;
	for(int i=0;i<n;i++){
		toys_small.push_back(mp(ii(W[i], S[i]), i));
		toys_light.push_back(mp(ii(W[i], S[i]), i));
	}
	sort(toys_small.begin(), toys_small.end(), s);
	sort(toys_light.begin(), toys_light.end());
	while(l<=r){
		int m = MID;
		

		int pos=0;
		int cnt=0;
		priority_queue<ii> pq;
		for(int i=0;i<n;i++) used[i] = false;
		for(int i=0;i<A;i++){
			while(pos<n && toys_light[pos].F.F<X[i]){
				pq.push(ii(toys_light[pos].F.S,toys_light[pos].S));
				pos++;
			}
			int x=m;
			while(pq.size()>0 && x>0){
				used[pq.top().S]=true;
				pq.pop();
				cnt++, x--;
			}

		}
		//cout<<"--------- "<<m<<" -----------\n";
		//cout<<pos<<endl;
		while(pq.size()>0)
			pq.pop();
		pos=0;

		for(int i=0;i<B;i++){
			while(pos<n && toys_small[pos].F.S<Y[i]){
				if(!used[toys_small[pos].S])
					pq.push(ii(toys_small[pos].F.F,toys_small[pos].S));
				pos++;
			}
			int x=m;
			while(pq.size()>0 && x>0){
				used[pq.top().S]=1;
				pq.pop();
				cnt++, x--;
			}

		}
		//cout<<cnt<<endl;
		//if(cnt==n) cout<<m<<endl;

		if(cnt==n) mm=m, r = m-1;
		else l = m+1;
	}
	return mm;
}

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