Submission #4294

#	Time	Username	Problem	Language	Result	Execution time	Memory
4294		cki86201	Robots (IOI13_robots)	C++98	100 / 100	1532 ms	27284 KiB

robots

#include "robots.h"
#include<algorithm>
#include<queue>
using namespace std;

const int MX = 1000010;
bool comp(const int *a,const int *b){return *a<*b;}
int *ord[MX];
int wn[MX],sn[MX];
int A,B,T;
typedef pair<int,int> P;
priority_queue <P>pq;

bool solve(int x)
{
	while(!pq.empty())pq.pop();
	int i,n;
	for(i=n=0;i<T;i++){
		while(*ord[i]!=n){
			int cnt=x;
			while(!pq.empty()&&cnt--)pq.pop();
			n++;
		}
		pq.push(P(sn[ord[i]-wn],*ord[i]));
	}
	while(A!=n){
		int tm=x;
		while(!pq.empty()&&tm--)pq.pop();
		n++;
	}
	int cnt=0;
	while(!pq.empty()){
		P tmp=pq.top();pq.pop();
		cnt++;
		if(cnt>(long long)(B-tmp.first)*x)return false;
	}
	return true;
}

int putaway(int A_, int B_, int T_, int X[], int Y[], int W[], int S[]) {
	A=A_,B=B_,T=T_;
	sort(X,X+A);
	sort(Y,Y+B);
	int i,n=0;
	for(i=0;i<T;i++)ord[i]=W+i;
	sort(ord,ord+T,comp);
	for(i=0;i<T;i++){
		while(n!=A&&*ord[i]>=X[n])n++;
		wn[ord[i]-W]=n;
	}
	for(i=0;i<T;i++)ord[i]=S+i;
	sort(ord,ord+T,comp);
	for(i=n=0;i<T;i++){
		while(n!=B&&*ord[i]>=Y[n])n++;
		sn[ord[i]-S]=n;
	}
	for(i=0;i<T;i++)ord[i]=wn+i;
	sort(ord,ord+T,comp);
	int st=T/(A+B),en=T,mi,ans=-1;
	while(st<=en){
		int mi=(st+en)>>1;
		if(solve(mi))ans=mi,en=mi-1;
		else st=mi+1;
	}
	return ans;
}

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