Submission #545364

#	Time	Username	Problem	Language	Result	Execution time	Memory
545364		benson1029	Robots (IOI13_robots)	C++14	100 / 100	1576 ms	24636 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];
priority_queue<int> st;
stack<int> stk;

bool check(int mid) {
	while(!stk.empty()) stk.pop();
	int ptr=0;
	for(int i=0; i<a; i++) {
		while(ptr < t && w[ptr].first < x[i]) {
			st.push(w[ptr].second);
			ptr++;
		}
		for(int j=0; j<mid; j++) {
			if(st.empty()) break;
			st.pop();
		}
	}
	while(ptr < t) {
		st.push(w[ptr].second);
		ptr++;
	}
	while(!st.empty()) {
		stk.push(st.top());
		st.pop();
	}
	for(int i=0; i<b; i++) {
		for(int j=0; j<mid; j++) {
			if(stk.empty()) break;
			if(stk.top() >= y[i]) break;
			stk.pop();
		}
	}
	if(stk.empty()) 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: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10