Submission #825100

#	Time	Username	Problem	Language	Result	Execution time	Memory
825100		pedroslrey	Robots (IOI13_robots)	C++17	14 / 100	3077 ms	47228 KiB

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 (stderr)

robots.cpp: In function 'void linesweep(std::vector<std::pair<int, int> >&, std::vector<bool>&, std::vector<int>&, int)':
robots.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for (int i = 0; i < points.size(); ++i)
      |                  ~~^~~~~~~~~~~~~~~
robots.cpp:12:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for (int i = 0; i < as.size(); ++i)
      |                  ~~^~~~~~~~~~~

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