Submission #798555

#	Time	Username	Problem	Language	Result	Execution time	Memory
798555		QwertyPi	Robots (IOI13_robots)	C++14	100 / 100	2644 ms	33156 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;
struct Robot{
	int x, y, id;
};

const int T_MAX = 1e6;
const int N_MAX = 5e4 + 11;
int W[T_MAX], S[T_MAX];
int A, B, T;
vector<int> rx, ry, rxi, ryi;
bool thrown[T_MAX];

struct BIT{
	int t[T_MAX];
	void init(){
		fill(t, t + T_MAX, 0);
	}
	void add(int p, int v){
		++p;
		for(int i = p; i < T_MAX; i += i & -i){
			t[i] += v;
		}
	}
	int qry(int p){
		++p; int res = 0;
		for(int i = p; i; i -= i & -i){
			res += t[i];
		}
		return res;
	}
	int bs(int v){
		int r = 0, s = 0;
		for(int j = 19; j >= 0; j--){
			if(s + t[r + (1 << j)] < v) s += t[r + (1 << j)], r += (1 << j);
		}
		return r;
	}
} bit;

bool can(int K){
	fill(thrown, thrown + T_MAX, 0);
	int ri = 0, s = 0; bit.init();
	for(int i = 0; i < A; i++){
		while(ri < T && W[rx[ri]] <= i){
			if(thrown[rx[ri]]) { ++ri; continue; }
			bit.add(ryi[rx[ri]], 1); ++ri; ++s;
		}
		for(int j = 0; j < K && s > 0; j++){
			int p = bit.bs(s); thrown[ry[p]] = true; --s;
			bit.add(p, -1);
		}
	}
	ri = s = 0; bit.init();
	for(int i = 0; i < B; i++){
		while(ri < T && S[ry[ri]] <= i){
			if(thrown[ry[ri]]) { ++ri; continue; }
			bit.add(rxi[ry[ri]], 1); ++ri; ++s;
		}
		for(int j = 0; j < K && s > 0; j++){
			int p = bit.bs(s); thrown[rx[p]] = true; --s;
			bit.add(p, -1);
		}
	}
	
	bool done = true;
	for(int i = 0; i < T; i++){
		if(!thrown[i]) done = false;
	}
	return done;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	::A = A; ::B = B; ::T = T; sort(X, X + A); sort(Y, Y + B);
	for(int i = 0; i < T; i++){
		::W[i] = upper_bound(X, X + A, W[i]) - X;
		::S[i] = upper_bound(Y, Y + B, S[i]) - Y;
		if(::W[i] == A && ::S[i] == B) return -1;
	}
	for(int i = 0; i < T; i++) rx.push_back(i); ry = rx;
	sort(rx.begin(), rx.end(), [](int a, int b){
		return ::W[a] < ::W[b];
	});
	sort(ry.begin(), ry.end(), [](int a, int b){
		return ::S[a] < ::S[b];
	});
	rxi.resize(T); ryi.resize(T);
	for(int i = 0; i < T; i++){
		rxi[rx[i]] = ryi[ry[i]] = i;
	}
	int L = 0, R = T;
	while(L != R){
		int M = (L + R) / 2;
		if(can(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:82:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   82 |  for(int i = 0; i < T; i++) rx.push_back(i); ry = rx;
      |  ^~~
robots.cpp:82:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   82 |  for(int i = 0; i < T; i++) rx.push_back(i); ry = rx;
      |                                              ^~

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