Submission #79379

#	Time	Username	Problem	Language	Result	Execution time	Memory
79379		shoemakerjo	Robots (IOI13_robots)	C++14	76 / 100	3050 ms	48620 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

#define maxn 50010
vector<int> sizes[maxn];
vector<int> ys;

int a, b;

bool check(int mid) {
	multiset<int> active;
	for (int i = 0; i < a; i++) {
		for (int vv : sizes[i]) active.insert(vv);
		
		for (int j = 0; j < mid; j++) {
			if (!active.size()) break;
			auto it = active.end();
			--it;
			active.erase(it);
		}
	}
	for (int vv : sizes[a]) active.insert(vv);

	// // cout << mid << " interim size: " << active.size() << endl;
	// for (int thing : active) {
	// 	cout << "    " << thing << endl;
	// }

	for (int cur : ys) {
		//go in order, starting with cur
		// cout << "  ---- cur: " << cur << endl;
		if (!active.size()) break;
		for (int j = 0; j < mid; j++) {
			if (!active.size()) break;
			auto it = active.lower_bound(cur);
			if (it == active.begin()) break;
			--it;
			active.erase(it);
		}
	}
	return active.size() == 0;

}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    int lo = 1, hi = T;
    //X is weight limits for A type robots
    //Y is size limits for B type robogts
    //limits cannot be equal

    a = A;
    b = B;

    sort(X, X+A);
    sort(Y, Y+B);

    // cout << "Array of A" << endl;
    // cout << "     ";
    // for (int i = 0; i < A; i++) cout << X[i] << " ";
    // cout << endl;

    for (int i = 0; i < B; i++) ys.push_back(Y[i]);

    for (int i = 0; i < T; i++) {
    	if ((A == 0 || W[i] >= X[A-1]) && 
    		(B == 0 || S[i] >= Y[B-1])) {
    		return -1;
    	}
    	//push back to largest A
    	int cw = W[i];
    	int cs = S[i];
    	int cl = 0;
    	int ch = A-1;
    	//manually doing the binary search thing
    	//find first guy this works for
    	if (A == 0 || cw >= X[A-1]) {
    		// cout <<"-->    " <<  cw << " " << cs << " " << A << endl;
    		sizes[A].push_back(cs);
    	}
    	else {
    		while (cl < ch) {
    			int mid = (cl+ch)/2;
    			if (X[mid] > cw) {
    				//this spot works
    				ch = mid;
    			}
    			else cl = mid+1; //does not work for this value
    		}
    		// cout << "-->   " << cw << " " << cs << " " << cl << endl;
    		sizes[cl].push_back(cs);
    	}

    }

    while (lo < hi) {
    	int mid = (lo+hi)/2;
    	if (check(mid)) {
    		// cout << "something worked" << endl;
    		hi = mid;
    	}
    	else lo = mid+1;
    }
    return lo;

}

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