Submission #897988

#	Time	Username	Problem	Language	Result	Execution time	Memory
897988		Muhammad_Aneeq	Robots (IOI13_robots)	C++17	39 / 100	3093 ms	27240 KiB

robots

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
 
#include <iostream>
#include <algorithm>
#include <set>
#include "robots.h"
using namespace std;
int const T=1e6+10,N=5e4+10;
pair<int,int>qu[T]={};
int a[N],b[N];
int n,m,t;
inline bool check(int o)
{
	multiset<int>d;
	int i=0,j=0;
	while (i<n&&j<t)
	{
		if (a[i]>qu[j].first)
		{
			d.insert(qu[j].second);
			j++;
		}
		else
		{
			int x=o;
			while (min(x,int(d.size())))
			{
				d.erase(--end(d));
				x--;
			}
			i++;
		}
	}
	if (j==t&&d.size()<=(n-i)*o)
		return 1;
	while (j<t)
	{
		d.insert(qu[j].second);
		j++;
	}
	j=0;
	while (j<m)
	{
		int x=o;
		while (min(x,int(d.size())))
		{
			if ((*begin(d))<b[j])
			{
				d.erase(begin(d));
				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=1e6;
	while(st+1<en)
	{
			int mid=(st+en)/2;
			if (check(mid))
				en=mid;
			else
				st=mid;
	}
	return en;
}

Compilation message (stderr)

robots.cpp: In function 'bool check(int)':
robots.cpp:38:20: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |  if (j==t&&d.size()<=(n-i)*o)
      |            ~~~~~~~~^~~~~~~~~

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