Submission #332048

#	Time	Username	Problem	Language	Result	Execution time	Memory
332048		zggf	Robots (IOI13_robots)	C++14	100 / 100	1830 ms	24596 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[]) {
	vector<pair<int, int>> R;
	for(int i = 0; i < T; i++){
		R.push_back(make_pair(W[i], S[i]));	
	}
	sort(R.begin(), R.end());

	sort(X, X+A);
	sort(Y, Y+B, greater<int>());
	
	int pocz = 0, kon = T+1;
	while(pocz<kon){
		int mid = (pocz+kon)/2;
		int pt = -1;
		priority_queue<int> mp;
		for(int i = 0; i < A; i++){
			int x = X[i];
			while((pt<T-1)&&R[pt+1].first<x){
				pt++;	
				mp.push(R[pt].second);	
			}	
			int tmp = mid;
			while(tmp&&!mp.empty()){
				mp.pop();
				tmp--;	
			}	
		}
		for(int i = pt+1; i < T; i++) mp.push(R[i].second);

		bool pos = true;
		for(int i = 0; i < B; i++){
			int tmp = mid;
			while(tmp&&!mp.empty()){
				int nwm = mp.top();
				if(nwm>=Y[i]) {pos = false; break;}
				mp.pop();
				tmp--;	
			}	
			if(!pos) break;
		}	
		if(!mp.empty()) pos = false;
		if(pos) kon = mid;
		else pocz = mid+1;
	}
	if(pocz==T+1) return -1;
	return pocz;
}

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