Submission #545314

#	Time	Username	Problem	Language	Result	Execution time	Memory
545314		benson1029	Robots (IOI13_robots)	C++14	76 / 100	3087 ms	35728 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;

int a,b,t;
int x[50005], y[50005];
pair<int,int> w[1000005];
multiset<int> st;

bool check(int mid) {
	int ptr=0;
	for(int i=0; i<a; i++) {
		while(ptr < t && w[ptr].first < x[i]) {
			st.insert(w[ptr].second);
			ptr++;
		}
		for(int j=0; j<mid; j++) {
			if(st.size()==0) break;
			st.erase(prev(st.end()));
		}
	}
	while(ptr < t) {
		st.insert(w[ptr].second);
		ptr++;
	}
	for(int i=0; i<b; i++) {
		for(int j=0; j<mid; j++) {
			if(st.size()==0) break;
			if(*st.begin() >= y[i]) break;
			st.erase(st.begin());
		}
	}
	if(st.size()==0) return true;
	return false;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    a = A; b = B; t = T;
    for(int i=0; i<a; i++) x[i] = X[i];
    for(int i=0; i<b; i++) y[i] = Y[i];
    sort(x, x+a); sort(y, y+b);
    for(int i=0; i<t; i++) {
    	w[i].first = W[i]; w[i].second = S[i];
    	if(w[i].first >= x[a-1] && w[i].second >= y[b-1]) {
    		return -1;
		}
	}
	sort(w, w+t);
	int l,r,mid;
	l = 1; r = t;
	while(l<r) {
		mid = (l+r)/2;
		if(check(mid)) r = mid;
		else l = mid+1;
	}
	return l;
}

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