Submission #291337

#	Time	Username	Problem	Language	Result	Execution time	Memory
291337		TMJN	Robots (IOI13_robots)	C++17	100 / 100	2870 ms	28628 KiB

robots

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

struct WS{
	int weight;
	int size;
};

bool compw(const WS &a,const WS &b){
	return a.weight<b.weight;
}

bool operator<(const WS &a,const WS &b){
	return a.size<b.size;
}

WS K[1000000];

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	sort(X,X+A);
	sort(Y,Y+B);
	for(int i=0;i<T;i++){
		K[i].weight=W[i];
		K[i].size=S[i];
	}
	sort(K,K+T,compw);
	int L,R;
	L=0;
	R=0xE869120;
	while(L+1!=R){
		int M=(L+R)/2;
		priority_queue<WS>pq;
		int p=0;
		for(int i=0;i<T;i++){
			while(p!=A&&X[p]<=K[i].weight){
				for(int j=0;j<M&&!pq.empty();j++){
					pq.pop();
				}
				p++;
			}
			pq.push(K[i]);
		}
		for(int i=p;i<A;i++){
			for(int j=0;j<M&&!pq.empty();j++){
				pq.pop();
			}
		}
		vector<int>v;
		while(!pq.empty()){
			v.push_back(pq.top().size);
			pq.pop();
		}
		reverse(v.begin(),v.end());
		for(int i=B-1;i>=0&&!v.empty();i--){
			if(Y[i]<=v.back())break;
			for(int j=0;j<M&&!v.empty();j++){
				v.pop_back();
			}
		}
		if(v.empty()){
			R=M;
		}
		else{
			L=M;
		}
	}
	if(R==0xE869120){
		return -1;
	}
	return R;
}

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