Submission #118565

#	Time	Username	Problem	Language	Result	Execution time	Memory
118565		eohomegrownapps	로봇 (IOI13_robots)	C++14	90 / 100	600 ms	65536 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	//a,x: weight robots
	//b,y: size robots
	//vector<vector<ll> > weightsize(A+1,vector<ll>(B+1,0));
	map<ll,ll> weightsize;
	ll cns = 100000;
	vector<pair<ll,ll> > weightbots; //weight, num
	/*vector<ll> weights(A);
	for (ll i = 0; i<A; i++){
		weights[i]=X[i];
	}
	sort(weights.begin(),weights.end());*/
	sort(X,X+A);
	ll currentWeight = -1;
	for (ll i = 0; i<A; i++){
		if (X[i]>currentWeight){
			currentWeight=X[i];
			weightbots.push_back(make_pair(currentWeight,ll(1)));
		} else {
			weightbots[weightbots.size()-1].second++;
		}
	}

	vector<pair<ll,ll> > sizebots; //size, num
	/*vector<ll> sizes(B);
	for (ll i = 0; i<B; i++){
		sizes[i]=Y[i];
	}
	sort(sizes.begin(),sizes.end());*/
	sort(Y,Y+B);
	ll currentsize = -1;
	for (ll i = 0; i<B; i++){
		if (Y[i]>currentsize){
			currentsize=Y[i];
			sizebots.push_back(make_pair(currentsize,ll(1)));
		} else {
			sizebots[sizebots.size()-1].second++;
		}
	}

	for (ll i = 0; i<T; i++){
		ll curw = W[i];
		ll curs = S[i];
		//find lowest w
		auto wi = upper_bound(weightbots.begin(),weightbots.end(),make_pair(curw+1,ll(0)));
		auto si = upper_bound(sizebots.begin(),sizebots.end(),make_pair(curs+1,ll(0)));
		if (wi==weightbots.end()&&si==sizebots.end()){
			return -1;
		} else {
			//cout<<curw<<" "<<curs<<" "<<wi-weightbots.begin()<<" "<<si-sizebots.begin()<<endl;
			weightsize[(wi-weightbots.begin())*cns+(si-sizebots.begin())]++;
		}
	}
	/*for (ll y = 0; y<B+1; y++){
		for (ll x = 0; x<A+1; x++){
			cout<<weightsize[x][y]<<"\t";
		}
		cout<<endl;
	}*/
	A=weightbots.size();
	B=sizebots.size();
	vector<ll> wptr(A,B);
	vector<ll> sptr(B,A);
	ll minutes = 0;
	ll wstartfrom = A-1;
	ll sstartfrom = B-1;
	while (true){
		bool nothingToRemove = true;
		ll cw = wstartfrom;
		if (cw>=0){
			for (ll i = weightbots.size()-1; i>=0; i--){
				//cout<<"weight bot "<<i<<endl;
				auto wb = weightbots[i];
				cw=min(cw,i);
				for (ll j = 0; j<wb.second; j++){
					while (cw>=0){
						while (wptr[cw]>=0&&weightsize[cw*cns+wptr[cw]]==0){
							wptr[cw]--;
						}
						if (wptr[cw]!=-1){
							break;
						} else {
							cw--;
							if (i==A-1){
								wstartfrom--;
							}
						}
					}
					if (cw==-1){
						break;
					}
					if(weightsize[cw*cns+wptr[cw]]>0){
						weightsize[cw*cns+wptr[cw]]--;
						//cout<<"removed "<<cw<<" "<<wptr[cw]<<endl;
						nothingToRemove=false;
					}
				}
				if (cw==-1){
					break;
				}
			}
		}

		ll cs = sstartfrom;
		if (cs>=0){
			for (ll i = sizebots.size()-1; i>=0; i--){
				//cout<<"size bot "<<i<<endl;
				auto sb = sizebots[i];
				cs=min(cs,i);
				for (ll j = 0; j<sb.second; j++){
					while (cs>=0){
						while (sptr[cs]>=0&&weightsize[sptr[cs]*cns+cs]==0){
							sptr[cs]--;
						}
						if (sptr[cs]!=-1){
							break;
						} else {
							cs--;
							if (i==B-1){
								sstartfrom--;
							}
						}
					}
					if (cs==-1){
						break;
					}
					if(weightsize[sptr[cs]*cns+cs]>0){
						weightsize[sptr[cs]*cns+cs]--;
						//cout<<"removed "<<cs<<" "<<sptr[cs]<<endl;
						nothingToRemove=false;
					}
				}
				if (cs==-1){
					break;
				}
			}
		}
		if (nothingToRemove){
			return minutes;
		} else {
			minutes++;
		}
	}
	//optimise?
}

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