Submission #825097

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
825097	2023-08-14T14:21:30 Z	pedroslrey	Robots (APIO13_robots)	C++17	Compilation error	0 ms	0 KB

robots

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "robots.h"

using namespace std;

void linesweep(vector<pair<int, int>> &points, vector<bool> &marc, vector<int> &as, int k) {
	vector<tuple<int, int, int>> events;
	for (int i = 0; i < points.size(); ++i)
		events.emplace_back(points[i].first, points[i].second, i);

	for (int i = 0; i < as.size(); ++i)
		events.emplace_back(as[i], 2e9, i);

	sort(events.begin(), events.end());

	set<pair<int, int>> toys;
	for (auto [x, y, idx]: events) {
		// cerr << "PROCESSING " << x << " " << y << " " << idx << "\n";
		if (y < 1e9 && !marc[idx]) toys.emplace(y, idx);
		else if (y == 2e9)
			for (int i = 0; i < k && !toys.empty(); ++i) {
				// cerr << idx << " TOOK TOY " << toys.rbegin()->second << "\n";
				marc[toys.rbegin()->second] = true;
				toys.erase(--toys.end());
			}
	}
	// cerr << "FINISH PART\n";
}

bool check(vector<pair<int, int>> &points, vector<int> &as, vector<int> &bs, int k) {
	vector<pair<int, int>> stniop;
	for (auto [x, y]: points)
		stniop.emplace_back(y, x);

	vector<bool> marc(points.size());
	linesweep(points, marc, as, k);
	linesweep(stniop, marc, bs, k);

	// cerr << "ANSWER: " << k << " ";

	for (bool b: marc)
		if (!b) {
			// cerr << "NO\n";
			return false;
		}
	// cerr << "YES\n";
	return true;
}

int putaway(int a, int b, int t, int as[], int bs[], int xs[], int ys[]) {
	vector<pair<int, int>> points;
	for (int i = 0; i < t; ++i)
		points.emplace_back(xs[i], ys[i]);

	vector<int> xlines, ylines;
	for (int i = 0; i < a; ++i)
		xlines.push_back(as[i]-1);

	for (int i = 0; i < b; ++i)
		ylines.push_back(bs[i]-1);

	xlines.push_back(0);
	ylines.push_back(0);

	sort(xlines.begin(), xlines.end());
	sort(ylines.begin(), ylines.end());

	for (auto [x, y]: points)
		if (x > xlines.back() && y > ylines.back()) return -1;

	int l = 0, r = t;
	while (l < r-1) {
		cerr << l << " " << r << "\n";
		int m = (l + r)/2;

		if (check(points, xlines, ylines, m)) r = m;
		else l = m;
	}
	return r;
}

Compilation message

robots.cpp:3:10: fatal error: robots.h: No such file or directory
    3 | #include "robots.h"
      |          ^~~~~~~~~~
compilation terminated.