Submission #30058

#	Time	Username	Problem	Language	Result	Execution time	Memory
30058		inqr	Robots (IOI13_robots)	C++14	90 / 100	3000 ms	14852 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rt insert
#define st first
#define nd second
#define ll long long
#define pii pair < int , int >
#define DB printf("debug\n");
using namespace std;
int wrc,src,tn;
vector < int  > wr;
vector < int > sr;
vector < pii > tws;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	wrc=A;src=B;tn=T;
	for(int i=0;i<tn;i++){
		tws.pb(mp(W[i],S[i]));
	}
	sort(tws.begin(),tws.end());
	for(int i=0;i<wrc;i++)wr.pb(X[i]);
	for(int i=0;i<src;i++)sr.pb(Y[i]);
	sort(wr.begin(),wr.end());
	sort(sr.begin(),sr.end());reverse(sr.begin(),sr.end());

	int l=0,r=tn+5,m,ans=1e9;
	priority_queue < int > pq;
	while(l<r){
		m=(l+r)/2;
		pq = priority_queue < int > ();
		//printf("l=%d r=%d m=%d\n",l,r,m);
		int twsind=0;
		for(int i=0;i<wrc;i++){// eklicegimiz robotu aldik
			//printf("	i=%d wrc=%d\n",i,wr[i]);
			for(int j=twsind;tws[j].st<wr[i] && j<tn;j++){//eklicemiz robota kalan olan toylari ekledik
				//printf("		j=%d tws= %d %d\n",j,tws[j].st,tws[j].nd);
				pq.push(tws[j].nd);
				twsind=j+1;
			}
			for(int j=0;j<m && pq.size();j++){
				//printf("		%d pop\n",pq.top());
				pq.pop();// m kadarlari pq dan attik
			}
		}
		for(int j=twsind;j<tn;j++){//eklicemiz robota kalan olan toylari ekledik
			//printf("j=%d tws= %d %d\n",j,tws[j].st,tws[j].nd);
			pq.push(tws[j].nd);
		}
		for(int i=0;i<src;i++){
			for(int j=0;j<m;j++){
				if(pq.size()){
					if(pq.top()<sr[i]){
						pq.pop();
					}
					else if(r==tn+5) return -1;
				}
			}
		}
		if(pq.size()){
			l=m+1;
		}
		else{
			r=m;
			ans=min(ans,m);
		}
	}
	if(ans==1e9)return -1;
    return ans;
}

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