Submission #287182

#	Time	Username	Problem	Language	Result	Execution time	Memory
287182		AMO5	Robots (IOI13_robots)	C++17	0 / 100	1 ms	512 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>;

multiset<ii>ww,ss;
//subtask 1,2

int putaway(int A,int B,int T, int X[],int Y[],int W[],int S[]){
	for(int i=0; i<T; i++){
		ww.insert({W[i],S[i]});
		ss.insert({S[i],W[i]});
	}
	sort(X,X+A);
	sort(Y,Y+B);
	auto it = ww.lower_bound(ii(X[A-1]+1,-1));
	while(it!=ww.end()){
		if(it->se>Y[B-1])return -1;
		it++;
	}
	
	if(A+B==2){
		if(A==2){
			if((ww.begin()->fi)>X[0])return 2;
			else return 1;
		}else if(A==1){
			if((ww.begin()->se)<=Y[0]&&(ww.rbegin()->fi)<=X[0])return 1;
			else if((ww.begin()->fi)<=X[0]&&(ww.rbegin()->se)<=Y[0])return 1;
			else return 2;
		}else{
			if((ss.begin()->fi)>Y[0])return 2;
			else return 1;
		}
	}
	
	if(B!=0)return -1;
	int t = 0;
	while(sz(ww)){
		//cerr<<sz(ww)<<" "<<sz(ss)<<"\n";
		for(int i=0; i<A; i++){
			if(ww.begin()->fi<=X[i]){
				ii now = *ww.begin();
				//cerr<<t<<":w "<<i<<" "<<X[i]<<" "<<now.fi<<" "<<now.se<<"\n";
				swap(now.fi,now.se);
				ww.erase(ww.begin());
				ss.erase(ss.find(now));
			}
		}
		for(int i=0; i<B; i++){
			if(ww.begin()->fi<=X[i]){
				ii now = *ss.begin();
				//cerr<<t<<":s "<<i<<" "<<Y[i]<<" "<<now.fi<<" "<<now.se<<"\n";
				swap(now.fi,now.se);
				ss.erase(ss.begin());
				ww.erase(ww.find(now));
			}
		}
		t++;
	}
	return t;
}
/*
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n,m,t; cin>>n>>m>>t;
	int x[n],y[m],w[t],s[t];
	for(int i=0; i<n; i++)cin>>x[i];
	for(int i=0; i<m; i++)cin>>y[i];
	for(int i=0; i<t; i++)
		cin>>w[i]>>s[i];
	cout<<putaway(n,m,t,x,y,w,s)<<endl;
	return 0;
}
*/ 

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

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