Submission #332037

#	Time	Username	Problem	Language	Result	Execution time	Memory
332037		zggf	Robots (IOI13_robots)	C++14	28 / 100	1777 ms	23132 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, vector<int>, greater<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.size()){
				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.size()){
				int nwm = mp.top();
				if(nwm>=Y[i]) {pos = false; break;}
				mp.pop();
				tmp--;	
			}	
			if(!pos) break;
		}	
		if(mp.size()) 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: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10