Submission #223658

#	Time	Username	Problem	Language	Result	Execution time	Memory
223658		mode149256	Robots (IOI13_robots)	C++14	0 / 100	3093 ms	49520 KiB

robots

/*input

*/
#include "robots.h"
#include <bits/stdc++.h>
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 toy &a, const toy &b) {
		return a.s > b.s or (a.s == b.s and a.i < b.i);
	}
};

struct byW {
	bool operator()(const toy &a, const toy &b) {
		return a.w > b.w or (a.w == b.w and a.i < b.i);
	}
};
vl weak, small;
vector<toy> toys;
int Wsz, Ssz;
int N;

bool gali(int S) {
	set<toy, byS> taken;
	vb been(N, false);

	int j = 0;

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

		for (int h = 0; h < S && taken.size(); ++h)
		{
			been[(*taken.begin()).i] = true;
			taken.erase(taken.begin());
		}
	}

	taken.clear();

	// {
	// 	taken.insert(toys[0]);
	// 	taken.insert(toys[1]);
	// 	printf("t0 = %d, t1 = %d, tkbeg = %d\n", toys[0].s,toys[1].s, (*taken.begin()).s);
	// 	taken.clear();
	// }

	for (int i = 0; i < N; ++i)
	{
		if (!been[i])
			taken.insert(toys[i]);
	}

	// printf("S = %d, been: ", S);
	// for (auto u : been) printf("%d ", (int)u);
	// printf("\n");

	for (auto u : small) {
		if (taken.empty()) break;
		if (u <= (*taken.begin()).s) return false;
		for (int i = 0; i < S and taken.size(); ++i)
			taken.erase(taken.begin());
	}

	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<toy>(T);
	sort(weak.begin(), weak.end());
	sort(small.rbegin(), small.rend());
	if (!A and !B) return -1;

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

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

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

	return l;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:143:7: warning: unused variable 'mxW' [-Wunused-variable]
   int mxW = 0;
       ^~~
robots.cpp:144:7: warning: unused variable 'mxS' [-Wunused-variable]
   int mxS = 0;
       ^~~

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