Submission #1278313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278313		WH8	Robots (IOI13_robots)	C++20	90 / 100	3095 ms	12240 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);
	vector<int> xp(A), yp(B);
	for(int i=0;i<A;i++)xp[i]=i;
	for(int i=0;i<B;i++)yp[i]=i;
	
	int itr=0;
	while(cnt < T){
		for(int i=A-1;i>=0;i--){
			if(i!=A-1)xp[i]=min(xp[i], xp[i+1]);
			while(xp[i] >= 0){
				while(!x[xp[i]].empty() and (done[x[xp[i]].back()]))x[xp[i]].pop_back();
				if(!x[xp[i]].empty()){
					done[x[xp[i]].back()]=true;
					cnt++;
					//~ printf("x %d takes position %d %d\n", i,W[x[ptr].back()], S[x[ptr].back()]);
					break;
					
				}
				xp[i]--;
				
			}
			//~ printf("itr %d, i %d, ptr %d\n", itr, i, ptr);
			//~ assert(ptr < A);
		}
		for(int i=B-1;i>=0;i--){
			if(i!=B-1)yp[i]=min(yp[i], i);
			while(yp[i] >= 0){
				while(!y[yp[i]].empty() and (done[y[yp[i]].back()]))y[yp[i]].pop_back();
				if(!y[yp[i]].empty()){
					done[y[yp[i]].back()]=true;
					cnt++;
					break;
				}
				yp[i]--;
			}
		}
		//~ 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