Submission #1013023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013023		pcc	Robots (IOI13_robots)	C++17	100 / 100	1165 ms	24764 KiB

robots

#include "robots.h"

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

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 1e6+10;

int N,M,K;
pii arr[mxn];
int weak[mxn],small[mxn];
priority_queue<int,vector<int>,less<int>> pq;

bool check(int num){
	while(!pq.empty())pq.pop();
	int ptr = 0;
	for(int i = 0;i<N;i++){
		while(ptr<K&&arr[ptr].fs<weak[i]){
			pq.push(arr[ptr].sc);
			ptr++;
		}
		for(int j = 0;j<num&&!pq.empty();j++){
			pq.pop();
		}
	}
	while(ptr<K){
		pq.push(arr[ptr].sc);
		ptr++;
	}
	for(int i = M-1;i>=0&&!pq.empty();i--){
		if(pq.top()>=small[i])return false;
		for(int j = 0;j<num&&!pq.empty();j++)pq.pop();
	}
	return pq.empty();
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	N = A,M = B,K = T;
	for(int i = 0;i<N;i++)weak[i] = X[i];
	for(int i = 0;i<M;i++)small[i] = Y[i];
	for(int i = 0;i<T;i++)arr[i] = pii(W[i],S[i]);
	sort(weak,weak+N);
	sort(small,small+M);
	sort(arr,arr+K);
	int l = 0,r = K+1;
	while(l != r){
		int mid = (l+r)>>1;
		if(check(mid))r = mid;
		else l = mid+1;
	}
	return (r>K?-1:r);
}

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