Submission #223665

#	Time	Username	Problem	Language	Result	Execution time	Memory
223665		mode149256	Robots (IOI13_robots)	C++14	100 / 100	2601 ms	41356 KiB

robots

/*input

*/
#include "robots.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

struct toy {
	ll s;
	ll w;
	int i;
};

struct byS {
	bool operator()(const pl &a, const pl &b) {
		return a.x < b.x or (a.x == b.x and a.y < b.y);
	}
};

vl weak, small;
vector<pl> toys;
int Wsz, Ssz;
int N;

bool gali(int S) {
	priority_queue<pl, vector<pl>, byS> taken;
	int j = 0;

	for (int i = 0; i < Wsz; ++i)
	{
		while (j < N and toys[j].y < weak[i]) {
			taken.push(toys[j]);
			j++;
		}

		for (int h = 0; h < S && taken.size(); ++h)
			taken.pop();
	}

	// {
	// 	while (taken.size()) taken.pop();

	// 	taken.push({10, -1});
	// 	taken.push({5, 167});

	// 	printf("%d\n", taken.top().x);
	// 	while (taken.size()) taken.pop();
	// }
	for (; j < N; ++j)
		taken.push(toys[j]);

	for (auto && u : small) {
		if (taken.empty()) break;
		if (u <= taken.top().x) return false;
		for (int i = 0; i < S and taken.size(); ++i)
			taken.pop();
	}

	return taken.empty();
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	Wsz = A;
	Ssz = B;
	N = T;
	for (int i = 0; i < A; ++i)
		weak.emplace_back(X[i]);
	for (int i = 0; i < B; ++i)
		small.emplace_back(Y[i]);

	toys = vector<pl>(T);
	sort(weak.begin(), weak.end());
	sort(small.rbegin(), small.rend());
	if (!A and !B) return -1;

	for (int i = 0; i < T; ++i) {
		toys[i] = {S[i], W[i]};
		if ((!B or S[i] >= small[0]) and (!A or W[i] >= weak.back())) return -1;
	}

	sort(toys.begin(), toys.end(), [](const pl & a, const pl & b) {
		// return a.w < b.w;
		return a.y < b.y;
	});

	int l = 1;
	int r = 1e6;
	int m;
	while (l < r) {
		m = (l + r) / 2;
		if (gali(m))
			r = m;
		else
			l = m + 1;
	}

	return l;
}

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