Submission #281764

#	Time	Username	Problem	Language	Result	Execution time	Memory
281764		amoo_safar	Robots (IOI13_robots)	C++17	100 / 100	484 ms	13384 KiB

robots

#include "robots.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int A, B, n, X[N], Y[N], W[N], S[N], I[N], ub[N];

int par[N], cnt[N];
int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}

bool Check(int x){
	//cerr << "! " << x << '\n';
	iota(par, par + A + 1, 0);
	for(int i = 0; i <= A; i++) cnt[i] = x;

	int nw = B - 1;
	int hp = x;
	for(int i = n - 1; i >= 0; i--){
		int bot = Find(ub[i]);
		if(bot < A){
			cnt[bot] --;
			if(cnt[bot] == 0) par[bot] = bot + 1;
			continue;
		}
		while( (nw >= 0) && ((hp == 0) || (S[i] >= Y[nw])) ){
			nw --;
			hp = x;
		}
		if(nw == -1) return false;
		hp --;
	}
	return true;
}

int putaway(int _A, int _B, int _n, int _X[], int _Y[], int _W[], int _S[]){
	A = _A; B = _B; n = _n;
	for(int i = 0; i < A; i++) X[i] = _X[i];
	for(int i = 0; i < B; i++) Y[i] = _Y[i];
	//for(int i = 0; i < n; i++) W[i] = _W[i];
	//for(int i = 0; i < n; i++) S[i] = _S[i];
	
	sort(X, X + A);
	sort(Y, Y + B);

	iota(I, I + n, 0);
	sort(I, I + n, [&](int i, int j){
		return _S[i] < _S[j];
	});
	for(int i = 0; i < n; i++) S[i] = _S[I[i]];
	for(int i = 0; i < n; i++) W[i] = _W[I[i]];
	for(int i = 0; i < n; i++)
		ub[i] = upper_bound(X, X + A, W[i]) - X;

	int up = n + 1;
	int L = 0, R = up, mid;
	while(L + 1 < R){
		mid = (L + R) >> 1;
		if(Check(mid))
			R = mid;
		else
			L = mid;
		//cerr << "# " << mid << '\n';
	}
	if(R == up) return -1;
	return R;
}

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