Submission #1278311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278311		WH8	Robots (IOI13_robots)	C++20	90 / 100	3095 ms	11724 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[]) {
	
	sort(X, X+A);
	sort(Y, Y+B);
	for(int i=0;i<A;i++)X[i]--;
	for(int i=0;i<B;i++)Y[i]--;
	vector<vector<int>> x(A), y(B);
	for(int i=0;i<T;i++){
		int tx=lower_bound(X, X+A, W[i])-X;
		if(tx < A){
			x[tx].push_back(i);
			//~ printf("%d %d going to %d\n", W[i], S[i],tx);
		}
		//~ else printf("not in %d %d\n",W[i],S[i]);
		if(W[i]>X[A-1] and S[i]>Y[B-1])return -1;
	}
	for(int i=0;i<T;i++){
		int ty=lower_bound(Y,Y+B,S[i])-Y;
		if(ty < B)y[ty].push_back(i);
	}
	for(int i=0;i<A;i++){
		sort(x[i].begin(),x[i].end(),[&](int a, int b){
			return S[a] < S[b];
		});
	}
	for(int i=0;i<B;i++){
		sort(y[i].begin(),y[i].end(),[&](int a,int b){
			return W[a] < W[b];
		});
	}
	int cnt=0;
	vector<bool> done(T, 0);
	int itr=0;
	while(cnt < T){
		int ptr;
		ptr=A-1;
		for(int i=A-1;i>=0;i--){
			ptr=min(ptr, i);
			while(ptr >= 0){
				while(!x[ptr].empty() and (done[x[ptr].back()]))x[ptr].pop_back();
				if(!x[ptr].empty()){
					done[x[ptr].back()]=true;
					cnt++;
					//~ printf("x %d takes position %d %d\n", i,W[x[ptr].back()], S[x[ptr].back()]);
					break;
					
				}
				ptr--;
				
			}
			//~ printf("itr %d, i %d, ptr %d\n", itr, i, ptr);
			//~ assert(ptr < A);
		}
		ptr=B-1;
		for(int i=B-1;i>=0;i--){
			ptr=min(ptr, i);
			while(ptr >= 0){
				while(!y[ptr].empty() and (done[y[ptr].back()]))y[ptr].pop_back();
				if(!y[ptr].empty()){
					done[y[ptr].back()]=true;
					cnt++;
					break;
				}
				ptr--;
			}
		}
		//~ for(int i=0;i<T;i++)cout<<done[i]<<" ";
		//~ cout<<endl;
		itr++;
		//~ if(itr > 4)break;
	}
	return itr;
}

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