Submission #986356

#	Time	Username	Problem	Language	Result	Execution time	Memory
986356		Pyqe	Robots (IOI13_robots)	C++17	100 / 100	1388 ms	31864 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long wg[2][50069];
pair<long long,long long> a[1000069];
priority_queue<long long> pq;

int putaway(int n,int m,int d,int wgg[],int wgg2[],int aa[],int aa2[])
{
	long long i,j,r,lh,rh,md,zz;
	
	for(i=1;i<=n;i++)
	{
		wg[0][i]=wgg[i-1];
	}
	sort(wg[0]+1,wg[0]+n+1);
	for(i=1;i<=m;i++)
	{
		wg[1][i]=wgg2[i-1];
	}
	sort(wg[1]+1,wg[1]+m+1);
	for(i=1;i<=d;i++)
	{
		a[i]={aa[i-1],aa2[i-1]};
	}
	sort(a+1,a+d+1);
	for(zz=-1,lh=1,rh=d;lh<=rh;)
	{
		md=(lh+rh)/2;
		for(;!pq.empty();pq.pop());
		for(j=0,i=1;i<=n+1;i++)
		{
			for(;j<d&&(i>n||a[j+1].fr<wg[0][i]);)
			{
				j++;
				pq.push(a[j].sc);
			}
			if(i<=n)
			{
				for(r=0;!pq.empty()&&r<md;pq.pop(),r++);
			}
		}
		for(i=m;i;i--)
		{
			if(!pq.empty()&&pq.top()>=wg[1][i])
			{
				break;
			}
			for(j=0;!pq.empty()&&j<md;pq.pop(),j++);
		}
		if(pq.empty())
		{
			zz=md;
			rh=md-1;
		}
		else
		{
			lh=md+1;
		}
	}
	return zz;
}

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