Submission #373620

#	Time	Username	Problem	Language	Result	Execution time	Memory
373620		cheissmart	Robots (IOI13_robots)	C++14	39 / 100	505 ms	65540 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") -> " << #x << " is " << (x) << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	vi a(A), b(B);
	V<pi> c(T);
	for(int i = 0; i < A; i++) a[i] = X[i];
	for(int i = 0; i < B; i++) b[i] = Y[i];
	for(int i = 0; i < T; i++) c[i] = MP(W[i], S[i]);
	sort(ALL(a)), sort(ALL(b)), sort(ALL(c), [&] (pi a, pi b) {
		return a.S < b.S;
	});
	auto ok = [&] (int k) { // each people can kill at msot k things
		multiset<int> ms, ms2;
		for(int i = A - 1; i >= 0; i--) {
			for(int j = 0; j < k; j++) {
				ms.insert(a[i]);
				if(ms.size() == T) break;
			}
		}
		for(int i = B - 1; i >= 0; i--) {
			for(int j = 0; j < k; j++) {
				ms2.insert(b[i]);
				if(ms2.size() == T) break;
			}
		}
		for(int i = T - 1; i >= 0; i--) {
			int x = c[i].F, y = c[i].S;
			if(ms.size() && ms.upper_bound(x) != ms.end()) {
				auto it = ms.upper_bound(x);
				ms.erase(it);
			} else {
				if(ms2.empty() || ms2.upper_bound(y) == ms2.end())
					return false;
				auto it = ms2.upper_bound(y);
				ms2.erase(it);
			}
		}
		return true;
	};

	int lb = 1, rb = T;
	while(lb <= rb) {
		int mb = (lb + rb) / 2;
		if(ok(mb)) rb = mb - 1;
		else lb = mb + 1;
	}
	if(lb > T) return -1;
	return lb;
}

Compilation message (stderr)

robots.cpp: In lambda function:
robots.cpp:34:18: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(ms.size() == T) break;
      |        ~~~~~~~~~~^~~~
robots.cpp:40:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     if(ms2.size() == T) break;
      |        ~~~~~~~~~~~^~~~

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