oj.uz

Submission #4290

# Submission time Handle Problem Language Result Execution time Memory
4290 2013-09-11T17:04:15 Z cki86201 Robots (IOI13_robots) C++
0 / 100
 0 ms 21136 KB 
#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;
#include<stdio.h>

bool solve(int x)
{
	if(x==1){
		x++;
		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--){
		//		printf("Pop %d %d\n",pq.top().first,pq.top().second);
				pq.pop();
			}
			n++;
		}
		pq.push(P(sn[ord[i]-wn],*ord[i]));
	//	printf("Pushing %d %d\n",sn[ord[i]-wn],*ord[i]);
	}
	while(A!=n){
		int tm=x;
		while(!pq.empty()&&tm--)pq.pop();
		n++;
	}
	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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 21136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 21136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21136 KB Output is correct
2 Incorrect 0 ms 21136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21136 KB Output is correct
2 Incorrect 0 ms 21136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21136 KB Output is correct
2 Incorrect 0 ms 21136 KB Output isn't correct
3 Halted 0 ms 0 KB -