Submission #825123

#	Time	Username	Problem	Language	Result	Execution time	Memory
825123		pedroslrey	Robots (IOI13_robots)	C++17	14 / 100	1589 ms	29660 KiB

robots

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

using namespace std;

void linesweep(vector<tuple<int, int, int>> &events, vector<bool> &marc, int k) {
	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<tuple<int, int, int>> &points, vector<tuple<int, int, int>> &stniop, int k, int n) {
	vector<bool> marc(n);
	linesweep(points, marc, k);
	linesweep(stniop, marc, 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;

	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 < xlines.size(); ++i)
		events.emplace_back(xlines[i], 2e9, i);

	vector<tuple<int, int, int>> stneve;
	for (int i = 0; i < points.size(); ++i)
		stneve.emplace_back(points[i].second, points[i].first, i);

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

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

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

		if (check(events, stneve, m, t)) r = m;
		else l = m;
	}
	return r;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:60: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]
   60 |  for (int i = 0; i < points.size(); ++i)
      |                  ~~^~~~~~~~~~~~~~~
robots.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (int i = 0; i < xlines.size(); ++i)
      |                  ~~^~~~~~~~~~~~~~~
robots.cpp:67: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]
   67 |  for (int i = 0; i < points.size(); ++i)
      |                  ~~^~~~~~~~~~~~~~~
robots.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for (int i = 0; i < ylines.size(); ++i)
      |                  ~~^~~~~~~~~~~~~~~

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