Submission #897996

#	Time	Username	Problem	Language	Result	Execution time	Memory
897996		Muhammad_Aneeq	Robots (IOI13_robots)	C++17	100 / 100	1294 ms	26264 KiB

robots

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
 
#include <iostream>
#include <algorithm>
#include <queue>
#include "robots.h"
using namespace std;
int const T=1e6+10,N=5e4+10;
pair<int,int>qu[T]={};
int a[N],b[N],n,m,t;
inline bool check(int o)
{
	priority_queue<int>d;
	int i=0,j=0;
	while (i<n&&j<t)
	{
		if (a[i]>qu[j].first)
		{
			d.push(qu[j].second);
			j++;
		}
		else
		{
			int x=o;
			while (min(x,int(d.size())))
			{
				d.pop();
				x--;
			}
			i++;
		}
	}
	while (i<n&&d.size())
	{
		int x=o;
		while (min(x,int(d.size())))
		{
			d.pop();
			x--;
		}
		i++;
	}
	if (j==t&&d.size()==0)
		return 1;
	while (j<t)
	{
		d.push(qu[j].second);
		j++;
	}
	j=m-1;
	while (j>=0)
	{
		int x=o;
		while (min(x,int(d.size())))
		{
			if (d.top()<b[j])
			{
				d.pop();
				x--;
			}
			else 
				break;
		}
		j--;
	}
	return (d.size()==0);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
	n=A;m=B;t=T;
	for (int i=0;i<n;i++)
	{
		a[i]=X[i];
	}
	for (int i=0;i<m;i++)
		b[i]=Y[i];
	sort(a,a+n);
	sort(b,b+m);
	int am=0,bm=0;
	if (n>0)
		am=a[n-1];
	if (m>0)
		bm=b[m-1];
	bool w=0;
	for (int i=0;i<t;i++)
	{
		qu[i].first=W[i];
		qu[i].second=S[i];
		if (qu[i].first>=am&&qu[i].second>=bm)
			w=1;
	}	
	if (w==1)
	{
		return -1;
	}
	sort(qu,qu+t);
	int st=t/(n+m)-1,en=t;
	while(st+1<en)
	{
			int mid=(st+en)/2;
			if (check(mid))
				en=mid;
			else
				st=mid;
	}
	return en;
}

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