Submission #400209

#	Time	Username	Problem	Language	Result	Execution time	Memory
400209		Jasiekstrz	Robots (IOI13_robots)	C++17	100 / 100	2164 ms	32820 KiB

robots

#include<bits/stdc++.h>
#include "robots.h"
#define fi first
#define se second
using namespace std;
const int TT=1e6;
struct Toy
{
	int w,s,id;
};
Toy t1[TT+10],t2[TT+10];
bool vis[TT+10];
priority_queue<pair<int,int>> pq;
bool comp1(Toy a,Toy b)
{
	return a.w<b.w;
}
bool comp2(Toy a,Toy b)
{
	return a.s<b.s;
}
bool ok(int A,int B,int T,int X[],int Y[],int c)
{
	for(int i=0;i<T;i++)
		vis[i]=false;
	while(!pq.empty())
		pq.pop();
	for(int i=0,j=0;i<A;i++)
	{
		while(j<T && t1[j].w<X[i])
		{
			pq.push({t1[j].s,t1[j].id});
			j++;
		}
		for(int it=1;it<=c && !pq.empty();it++)
		{
			vis[pq.top().se]=true;
			pq.pop();
		}
	}
	for(int i=B-1,j=T-1;i>=0;i--)
	{
		for(int it=1;it<=c;)
		{
			if(j<0)
				return true;
			if(vis[t2[j].id])
				j--;
			else if(t2[j].s>=Y[i])
				return false;
			else
			{
				vis[t2[j].id]=true;
				it++;
				j--;
			}
		}
	}
	for(int i=0;i<T;i++)
	{
		if(!vis[i])
			return false;
	}
	return true;
}
int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[])
{
	sort(X,X+A);
	sort(Y,Y+B);
	for(int i=0;i<T;i++)
		t1[i]=t2[i]={W[i],S[i],i};
	sort(t1,t1+T,comp1);
	sort(t2,t2+T,comp2);
	int bg=1,en=T;
	while(bg<en)
	{
		int mid=(bg+en)/2;
		if(ok(A,B,T,X,Y,mid))
			en=mid;
		else
			bg=mid+1;
	}
	if(ok(A,B,T,X,Y,bg))
		return bg;
	return -1;
}

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