제출 #897976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
897976		Muhammad_Aneeq	로봇 (IOI13_robots)	C++17	76 / 100	3070 ms	32852 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;
bool check(int o)
{
	multiset<pair<int,int>>d;
	int i=0,j=0;
	while (i<n&&j<t)
	{
		if (a[i]>qu[j].first)
		{
			d.insert({qu[j].second,j});
			j++;
		}
		else
		{
			int x=o;
			while (min(x,int(d.size())))
			{
				d.erase(--end(d));
				x--;
			}
			i++;
		}
	}
	while (i<n)
	{
		int x=o;
		while (min(x,int(d.size())))
		{
			d.erase(--end(d));
			x--;
		}
		i++;
	}
	while (j<t)
	{
		d.insert({qu[j].second,j});
		j++;
	}
	j=0;
	while (j<m)
	{
		int x=o;
		while (min(x,int(d.size())))
		{
			if ((*begin(d)).first<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=0,en=1e6+10;
	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: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10