제출 #4289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4289		cki86201	로봇 (IOI13_robots)	C++98	0 / 100	0 ms	21136 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]));
	}
	if(*ord[T-1]<A){
		int tm=x;
		while(!pq.empty()&&tm--)pq.pop();
	}
	n=B-1;
	int cnt=0;
	int r = pq.size();
	while(!pq.empty()){
		P tmp = pq.top();
		if(tmp.first==B)return false;
		while(tmp.first!=n)cnt=0,n--;
		pq.pop(),cnt++;
		if(cnt>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++)printf("%d %d\n",wn[i],sn[i]);
	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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10