Submission #409524

#	Time	Username	Problem	Language	Result	Execution time	Memory
409524		Belgutei	Robots (IOI13_robots)	C++17	100 / 100	1712 ms	22456 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define ll long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int l,r,ans,mid;
priority_queue<int> pq;
pair<int,int> p[1000005];
bool used[1000005];

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	l=0;
	r=T;
	sort(X,X+A);
	sort(Y,Y+B);
	
	for(int i=0; i<T; i++){
		p[i].ff=W[i];
		p[i].ss=S[i];
		if(p[i].ff>=X[A-1] && p[i].ss>=Y[B-1]) return -1;
	}
	
	sort(p,p+T);
	bool check=0;
	while(l<r){
		mid=(l+r)/2;
		int pos=0;
		// 0->(pos-1)
		while(pq.size()>0) pq.pop();
		for(int i=0; i<A; i++){
			// X[i]
			bool ok=0;
			for(int j=pos; j<T; j++){
				if(p[j].ff<X[i]){
					pq.push(p[j].ss);
				}
				else{
					ok=1;
					pos=j;
					break;
				}
			}
			if(ok==0) pos=T;
			int cnt=mid;
			while(cnt>0 && pq.size()>0){
				pq.pop();
				cnt--;
			}
		}
		for(int i=pos; i<T; i++) pq.push(p[i].ss);
		for(int i=B-1; i>=0; i--){
			int cnt=mid;
			while(cnt>0 && pq.size()>0 && pq.top()<Y[i]){
				pq.pop();
				cnt--;
			}
			if(cnt>0) break;
		}
		if(pq.size()==0){
			r=mid;
			check=1; 
		}
		else l=mid+1;
	}
	return l;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:31:7: warning: variable 'check' set but not used [-Wunused-but-set-variable]
   31 |  bool check=0;
      |       ^~~~~

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