Submission #411579

#	Time	Username	Problem	Language	Result	Execution time	Memory
411579		Mlxa	Robots (IOI13_robots)	C++14	76 / 100	3083 ms	19088 KiB

robots

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "robots.h"

const int N = 1 << 16;
const int M = 1e6 + 10;
const int INF = 1e9;
const pii NO = {-INF, -1};

void build(pii t[]) {
	for (int i = N - 1; i > 0; --i) {
		t[i] = max(t[i + i], t[i + i + 1]);
	}
}
pii query(pii t[], int l, int r) {
	pii res = NO;
	for (l += N, r += N; l <= r; l /= 2, r /= 2) {
		if (l % 2 == 1) {
			res = max(res, t[l++]);
		}
		if (r % 2 == 0) {
			res = max(res, t[r--]);
		}
	}
	return res;
}
void update(pii t[], int i, pii p) {
	t[i += N] = p;
	for (i /= 2; i > 0; i /= 2) {
		t[i] = max(t[i + i], t[i + i + 1]);
	}
}

vector<pii> byx[N], byy[N];
pair<int, int> tx[2 * N], ty[2 * N];

bool used[M];

bool check(int k, int a, int b, int t, int w[], int s[]) {
	fill_n(used, t, false);
	for (int i = 0; i < N; ++i) {
		byx[i].clear(), byy[i].clear();
	}
	for (int i = 0; i < t; ++i) {
		byx[w[i]].emplace_back(s[i], i);
		byy[s[i]].emplace_back(w[i], i);
	}
	for (int i = 0; i < N; ++i) {
		sort(all(byx[i]));
		sort(all(byy[i]));
		tx[i + N] = byx[i].size() ? byx[i].back() : NO;
		ty[i + N] = byy[i].size() ? byy[i].back() : NO;
	}
	build(tx), build(ty);
	for (int i = 0; i < a; ++i) {
		for (int it = 0; it < k; ++it) {
			int j = query(tx, 0, i).y;
			while (j >= 0 && used[j]) {
				assert(byx[w[j]].size() && byx[w[j]].back().y == j);
				byx[w[j]].pop_back();
				update(tx, w[j], byx[w[j]].size() ? byx[w[j]].back() : NO);
				j = query(tx, 0, i).y;
			}
			if (j < 0) {
				break;
			}
			// cout << i << " " << j << endl;
			used[j] = true;
		}
	}
	for (int i = 0; i < b; ++i) {
		for (int it = 0; it < k; ++it) {
			int j = query(ty, 0, i).y;
			while (j >= 0 && used[j]) {
				assert(byy[s[j]].size());
				assert(byy[s[j]].back().y == j);
				byy[s[j]].pop_back();
				update(ty, s[j], byy[s[j]].size() ? byy[s[j]].back() : NO);
				j = query(ty, 0, i).y;
			}
			if (j < 0) {
				break;
			}
			used[j] = true;
		}
	}
	return !count(used, used + t, false);
}

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
	sort(x, x + a);
	sort(y, y + b);
	for (int i = 0; i < t; ++i) {
		w[i] = (int)(upper_bound(x, x + a, w[i]) - x);
		s[i] = (int)(upper_bound(y, y + b, s[i]) - y);
	}
	int lef = 0, rig = t;
	if (!check(rig, a, b, t, w, s)) {
		return -1;
	}
	while (rig - lef > 1) {
		int mid = (lef + rig) / 2;
		if (check(mid, a, b, t, w, s)) {
			rig = mid;
		} else {
			lef = mid;
		}
	}
	return rig;
}

#ifdef LC
#include "grader.c"
#endif

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