Submission #234245

#	Time	Username	Problem	Language	Result	Execution time	Memory
234245		tinjyu	Robots (IOI13_robots)	C++14	100 / 100	1919 ms	29048 KiB

robots

#include "robots.h"
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
	int w,s;
}id[1000004];
long long int temp[1000005],a,b,t,x[1000005],y[1000005],num[1000005];
bool cmp2(long long int tmp1,long long int tmp2)
{
	return tmp1<tmp2;
}
long long int check(int m)
{
	//cout<<m<<endl;
	long long int p1=t-1,p2=a-1,now=0;
	num[0]=0;
	while(p1>=0 || p2>=0)
	{
		//cout<<id[p1].w<<" "<<x[p2]<<endl;
		temp[0]=0;
		while((id[p1].w>=x[p2] || p2==-1) && p1>=0)
		{
			temp[0]++;
			temp[temp[0]]=id[p1].s;
			p1--;
		}
		sort(temp+1,temp+temp[0]+1,cmp2);
		for(int i=1;i<=temp[0]-now;i++)
		{
			num[0]++;
			num[num[0]]=temp[i];
		}
		now=max(now-temp[0],(long long int )0);
		if(x[p2]>id[p1].w || p1==-1)
		{
			now+=m;
			p2--;
		}
	}
	sort(num+1,num+num[0]+1,cmp2);
	//for(int i=1;i<=num[0];i++)cout<<num[i]<<" ";
	//cout<<endl;
	p1=num[0],p2=b-1;
	if(p1==0)return 1;
	long long int tmpnum=m;
	while(p1>=1 && p2>=0)
	{
		if(tmpnum==0)
		{
			tmpnum=m;
			p2--;
		}
		if(y[p2]>num[p1])
		{
			p1--;
		}
		else 
		{
			//cout<<num[p1]<<" "<<y[p2]<<endl;
			return 0;
		}
		tmpnum--;

	}
	if(p1==0)return 1;
	return 0;
}
bool cmp1(const node &tmp1,const node &tmp2)
{
	return tmp1.w<tmp2.w || (tmp1.w==tmp2.w && tmp1.s<tmp2.s);
}
 
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    a=A;
    b=B;
    t=T;
    for(int i=0;i<a;i++)x[i]=X[i];
    for(int i=0;i<b;i++)y[i]=Y[i];
    for(int i=0;i<t;i++)
    {
    	id[i].w=W[i];
    	id[i].s=S[i];
	}
	long long int l=1,r=t,ans=-1;
	sort(id,id+t,cmp1);
	for(int i=0;i<t;i++)
	{
		//cout<<id[i].w<<" "<<id[i].s<<endl;
	}
	sort(x,x+a,cmp2);
	sort(y,y+b,cmp2);
	while(l<=r)
	{
		long long int mid=(l+r)/2;
		if(check(mid)==1)
		{
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	return ans;
}

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