Submission #1278316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278316		WH8	로봇 (IOI13_robots)	C++20	90 / 100	3096 ms	12208 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;
	auto par = [&](auto par, int c, vector<int> & p) -> int {
		//~ cout<<c<<endl;
		if(p[c]==c)return c;
		return p[c]=par(par, p[c], p);
	};
	auto merge = [&](int a, int b, vector<int> & p) {
		if(a < 0 or b<0)return;
		int pa=par(par, a, p), pb=par(par, b, p);
		if(pa==pb)return;
		if(pa > pb) swap(pa, pb);
		p[pb]=pa;
	};
	int itr=0;
	while(cnt < T){
		for(int i=A-1;i>=0;i--){
			int cp=par(par, i, xp);
			while(cp >= 0){
				while (!x[cp].empty() && done[x[cp].back()])
					x[cp].pop_back();
				if(!x[cp].empty()){ 
					done[x[cp].back()]=true;
					cnt++;
					//~ printf("x %d takes position %d %d\n", i,W[x[cp].back()], S[x[cp].back()]);
					break;
					
				}
				else{
					merge(cp, cp-1, xp);
					if(cp==0)break;
				}
				cp=par(par, i, xp);
			}
			//~ printf("itr %d, i %d, cp %d\n", itr, i, cp);
			//~ assert(ptr < A);
		}
		for(int i=B-1;i>=0;i--){
			int cp=par(par, i, yp);
			while(cp >= 0){
				while(!y[cp].empty() and (done[y[cp].back()]))y[cp].pop_back();
				if(!y[cp].empty()){
					done[y[cp].back()]=true;
					cnt++;
					break;
				}
				else {
					merge(cp, cp-1, yp);
					if(cp==0)break;
				}
				cp=par(par, i, yp);
			}
		}
		//~ 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