Submission #104522

#	Time	Username	Problem	Language	Result	Execution time	Memory
104522		hugo_pm	Robots (IOI13_robots)	C++17	100 / 100	2169 ms	13988 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= b; --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int INF = (int)(1e9);

const int maxToys = 1000*1000 + 5;
const int maxRobots = 50*1000 + 5;

int nbToys, nbWeak, nbSmall;
vector<pii> toys;
vector<int> weak;
vector<int> small;


bool can(int temps)
{
	priority_queue<int> ts;
	int indToy = 0;
	form(indWeak, nbWeak) {
		int lim = weak[indWeak];
		while (indToy < nbToys && toys[indToy].fi < lim) {
			ts.push(toys[indToy].se);
			++indToy;
		}
		int reste = temps;
		while (ts.empty() == false && reste > 0) {
			ts.pop();
			--reste;
		}
	}

	while (indToy < nbToys) {
		ts.push(toys[indToy].se);
		++indToy;
	}

	ford(indSmall, nbSmall) {
		int lim = small[indSmall];
		int reste = temps;
		while (ts.empty() == false && reste > 0 && ts.top() < lim) {
			ts.pop();
			--reste;
		}
	}

	return ts.empty();
}


int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	nbToys = T; nbWeak = A; nbSmall = B;

	toys.resize(nbToys);
	form(i, nbToys) toys[i] = pii {W[i], S[i]};
	sort(toys.begin(), toys.end());

	weak.resize(nbWeak);
	form(i, nbWeak) weak[i] = X[i];
	sort(weak.begin(), weak.end());

	small.resize(nbSmall);
	form(i, nbSmall) small[i] = Y[i];
	sort(small.begin(), small.end());

	int bgauche = 1, bdroite = maxToys;
	if (! can(bdroite)) return -1;
	while (bgauche < bdroite) {
		int bmid = (bgauche + bdroite) / 2;
		if (can(bmid)) bdroite = bmid;
		else bgauche = bmid + 1;
	}

	return bgauche;
}

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