Submission #411536

#	Time	Username	Problem	Language	Result	Execution time	Memory
411536		Mlxa	Robots (IOI13_robots)	C++14	76 / 100	323 ms	19636 KiB

robots

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "robots.h"

const int N = 5e4 + 10;

bool used[N];

void iter(int a, int b, int t, int x[], int y[], int w[], int s[]) {
	// cout << "iter " << a << " " << b << " " << t << endl;
	for (int i = 0; i < a; ++i) {
		int mx = -1;
		for (int j = 0; j < t; ++j) {
			if (used[j] || w[j] >= x[i]) {
				continue;
			}
			if (mx == -1 || s[mx] < s[j]) {
				mx = j;
			}
		}
		if (mx != -1) {
			// cout << "take w " << w[i] << ": " << x[mx] << " " << y[mx] << endl;
			used[mx] = true;
		}
	}
	for (int i = 0; i < b; ++i) {
		int mx = -1;
		for (int j = 0; j < t; ++j) {
			if (used[j] || s[j] >= y[i]) {
				continue;
			}
			if (mx == -1 || w[mx] < w[j]) {
				mx = j;
			}
		}
		if (mx != -1) {
			// cout << "take s " << s[i] << ": " << x[mx] << " " << y[mx] <<  " @" << mx << endl;
			used[mx] = true;
		}
	}
}

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
	sort(x, x + a);
	sort(y, y + b);
	int ti = 0;
	while (1) {
		int was = (int)count(used, used + t, true);
		if (was == t) {
			break;
		}
		++ti;
		iter(a, b, t, x, y, w, s);
		int now = (int)count(used, used + t, true);
		if (was == now) {
			return -1;
		}
	}
	return ti;
}

#ifdef LC
#include "grader.c"
#endif

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