Submission #798533

#	Time	Username	Problem	Language	Result	Execution time	Memory
798533		QwertyPi	Robots (IOI13_robots)	C++14	76 / 100	199 ms	65536 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;
vector<Robot> r, rx, ry;
bool thrown[T_MAX];

struct BIT{
	vector<int> t[N_MAX];
	void add(int v, int x){
		++v;
		for(int i = v; i < N_MAX; i += i & -i){
			t[i].push_back(x);
		}
	}
	int qry(int v, bool type_y){
		++v; int best = -1;
		for(int i = v; i; i -= i & -i){
			while(!t[i].empty() && thrown[t[i].back()]) t[i].pop_back();
			if(!t[i].empty() && (best == -1 || (type_y ? r[t[i].back()].y > r[best].y : r[t[i].back()].x > r[best].x))){
				best = t[i].back();
			}
		}
		return best;
	}
} bit_x, bit_y;
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] = 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++) r.push_back({W[i], S[i], i}); rx = ry = r;
	sort(rx.begin(), rx.end(), [](const Robot& a, const Robot& b){
		return a.x < b.x;
	});
	sort(ry.begin(), ry.end(), [](const Robot& a, const Robot& b){
		return a.y < b.y;
	});
	for(int i = 0; i < T; i++){
		bit_x.add(ry[i].x, ry[i].id);
		bit_y.add(rx[i].y, rx[i].id);
	}
	int done = 0, ans = 0;
	while(done < T){
		for(int i = 0; i < A; i++){
			int q = bit_x.qry(i, false);
			if(q != -1) done++, thrown[q] = true;
		}
		for(int i = 0; i < B; i++){
			int q = bit_y.qry(i, true);
			if(q != -1) done++, thrown[q] = true;
		}
		ans++;
	}
    return ans;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:40:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   40 |  for(int i = 0; i < T; i++) r.push_back({W[i], S[i], i}); rx = ry = r;
      |  ^~~
robots.cpp:40:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |  for(int i = 0; i < T; i++) r.push_back({W[i], S[i], i}); rx = ry = r;
      |                                                           ^~

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