Submission #287523

#	Time	Username	Problem	Language	Result	Execution time	Memory
287523		AMO5	Robots (IOI13_robots)	C++17	100 / 100	2160 ms	28528 KiB

robots

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

using namespace std;

#define fi first
#define se second
#define sz(x) (int)x.size()
using ii = pair<int,int>;
const int mxn = 1e6+5;
int n;
ii val[mxn];

struct node{
	int x,y;
	node(int x_, int y_):x(x_),y(y_){
	}
	bool operator < (const node &rhs)const{
		return y<rhs.y;
	}
};

bool works(int tar, int x[], int a, int y[], int b){
	priority_queue<node>pq;
	//cerr<<tar<<": \n";
	int ptr = 0;
	for(int i=0; i<a; i++){
		while(ptr<n&&val[ptr].fi<x[i])pq.emplace(node(val[ptr].fi,val[ptr].se)),ptr++;
		int cnt = 0;
		while(cnt<tar){
			if(!pq.empty())pq.pop(),cnt++;
			else break;
		}
	}
	while(ptr<n)pq.emplace(node(val[ptr].fi,val[ptr].se)),ptr++;
	for(int i=0; i<b; i++){
		int cnt = 0;
		while(cnt<tar){
			if(!pq.empty()&&pq.top().y<y[i])pq.pop(),cnt++;
			else break;
		}
	}
	//cerr<<sz(pq)<<"\n";
	return sz(pq)==0;
}

int putaway(int A,int B,int T, int X[],int Y[],int W[],int S[]){
	sort(X,X+A);
	sort(Y,Y+B,greater<int>());
	n=T;
	for(int i=0; i<T; i++){
		val[i]={W[i],S[i]};
	}
	sort(val,val+n,[&](const ii x, const ii y){
		return x.fi<y.fi;
	});
	int lo = 1, hi = T+5, ans = T;
	if(!works(T,X,A,Y,B))return -1;
	while(lo<=hi){
		int mid=(lo+hi)/2;
		if(works(mid,X,A,Y,B)){
			hi=mid-1;
			ans = mid;
		}else{
			lo=mid+1;
		}
	}
	return ans;
}
/*
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n2,m2,t2; cin>>n2>>m2>>t2;
	int x2[n2],y2[m2],w2[t2],s2[t2];
	for(int i=0; i<n2; i++)cin>>x2[i];
	for(int i=0; i<m2; i++)cin>>y2[i];
	for(int i=0; i<t2; i++)
		cin>>w2[i]>>s2[i];
	cout<<putaway(n2,m2,t2,x2,y2,w2,s2)<<endl;
	return 0;
}
// */ 

//check for -1 both w[i]&s[i] exceed largest x[i]&y[i]

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