Submission #328227

#	Time	Username	Problem	Language	Result	Execution time	Memory
328227		sofapuden	Robots (IOI13_robots)	C++14	100 / 100	1893 ms	24796 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e4;
int a, b, t;
vector<array<int,2>> toy;
vector<int> x, y;

bool check(int cur){
	priority_queue<int> PQ;
	for(int i = 0, cn = 0; i <= a; ++i){
		for(;cn < t && toy[cn][0] < x[i]; ++cn){
			PQ.push(toy[cn][1]);
		}
		if(i != a){
			for(int j = 0; j < cur; ++j){
				if(PQ.empty())break;
				PQ.pop();
			}
		}
	}
	for(int i = b-1; i >= 0; --i){
		for(int j = 0; j < cur; ++j){
			if(PQ.empty())break;
			if(PQ.top() >= y[i])break;
			PQ.pop();
		}
	}
	return PQ.empty();
}

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.push_back(X[i]);
    for(int i = 0; i < b; ++i)y.push_back(Y[i]);
    for(int i = 0; i < t; ++i)toy.push_back({W[i],S[i]});  
    x.push_back((int)2e9+5);
    sort(toy.begin(),toy.end());
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    
    int l = 1, r = t;
    
    while(l < r){
		int mid = (l+r)>>1;
		if(check(mid))r = mid;
		else l = mid+1;
	}
	return (check(l) ? l : -1);
}

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