Submission #373662

#	Time	Username	Problem	Language	Result	Execution time	Memory
373662		cheissmart	Robots (IOI13_robots)	C++14	39 / 100	3096 ms	15432 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") -> " << #x << " is " << (x) << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e6 + 1e5 + 100;

struct bit {
	int bit[N], tot;
	void clear() {
		memset(bit, 0, sizeof bit);
		tot = 0;
	}
	void add(int pos, int val) {
		tot += val;
		for(; pos < N; pos += pos & -pos)
			bit[pos] += val;
	}
	int psum(int pos) {
		int res = 0;
		for(; pos; pos -= pos & -pos)
			res += bit[pos];
		return res;
	}
	int qry(int i) {
		int want = psum(i), s = 0, now = 0;
		if(tot <= want) return -1;
		for(int j = 20; j >= 0; j--) {
			if(s + (1 << j) < N && now + bit[s + (1 << j)] <= want) {
				now += bit[s + (1 << j)];
				s += 1 << j;
			}
		}
		return s + 1;
	}
} bit1;

int putaway(int A, int B, int T, int a[], int b[], int W[], int S[]) {
	sort(a, a + A), sort(b, b + B);
	vi p(T);
	iota(ALL(p), 0);
	sort(ALL(p), [&] (int a, int b) {
		return S[a] < S[b];
	});
	vi compress;
	for(int i = 0; i < A; i++) compress.PB(a[i]);
	for(int i = 0; i < B; i++) compress.PB(b[i]);
	for(int i = 0; i < T; i++) compress.PB(W[i]), compress.PB(S[i]);
	sort(ALL(compress));
	compress.resize(unique(ALL(compress)) - compress.begin());
	auto go = [&] (int& x) {
		return x = lower_bound(ALL(compress), x) - compress.begin() + 1;
	};
	for(int i = 0; i < A; i++) go(a[i]);
	for(int i = 0; i < B; i++) go(b[i]);
	for(int i = 0; i < T; i++) go(W[i]), go(S[i]);
	auto ok = [&] (int k) { // each people can kill at msot k things
		bit1.clear();
		int tt = T;
		for(int i = A - 1; i >= 0 && tt > 0; i--) {
			bit1.add(a[i], k);
			tt -= k;
		}
		bool ok = true;
		vi need;
		for(int i = T - 1; i >= 0; i--) {
			int x = W[p[i]], y = S[p[i]];
			int pos = bit1.qry(x);
			if(pos != -1) {
				bit1.add(pos, -1);
			} else {
				need.PB(y);
			}
		}
		// need is sorted
		for(int i = int(need.size()) - 1, j = B - 1; i >= 0; i--) {
			if(j >= 0 && b[j] > need[i]) j--;
			int have = int(need.size()) - i, can = B - 1 - j;
			if(can == 0 || (have + can - 1) / can > k)
				return false;
		}
		return true;
	};

	int lb = 1, rb = T;
	while(lb <= rb) {
		int mb = (lb + rb) / 2;
		if(ok(mb)) rb = mb - 1;
		else lb = mb + 1;
	}
	if(lb > T) return -1;
	return lb;
}

Compilation message (stderr)

robots.cpp: In lambda function:
robots.cpp:76:8: warning: unused variable 'ok' [-Wunused-variable]
   76 |   bool ok = true;
      |        ^~

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