Submission #1219612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219612		boclobanchat	Robots (IOI13_robots)	C++20	100 / 100	1251 ms	13928 KiB

robots

#include"robots.h"
#include<bits/stdc++.h>
using namespace std;
int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[])
{
	vector< pair<int,int> > vi;
	for(int i=0;i<T;i++) vi.push_back({W[i],S[i]});
	sort(vi.begin(),vi.end());
	sort(X,X+A);
	sort(Y,Y+B,greater<int>());
	int l=1,r=T,ans=-1;
	while(l<=r)
	{
		int mid=(l+r)/2,p=A-1,resd=mid;
		priority_queue<int> pq;
		vector<int> w;
		for(int i=T-1;i+1;i--) if(vi[i].first>=X[A-1]) w.push_back(vi[i].second);
		else
		{
			while(p>0&&vi[i].first<X[p-1])
			{
				while(resd>0&&!pq.empty()) pq.pop(),resd--;
				while(!pq.empty()) w.push_back(pq.top()),pq.pop();
				p--,resd+=mid;
			}
			pq.push(vi[i].second);
		}
		while(resd>0&&!pq.empty()) pq.pop(),resd--;
		while(!pq.empty()) w.push_back(pq.top()),pq.pop();
		sort(w.begin(),w.end(),greater<int>());
		int f=mid,pt=0;
		bool ck=true;
		for(auto v:w)
		{
			if(f==0) pt++,f=mid;
			if(pt==B||v>=Y[pt])
			{
				ck=false;
				break;
			}
			f--;
		}
		if(!ck) l=mid+1;
		else r=mid-1,ans=mid;
	}
	return ans;
}

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