Submission #123813

#	Time	Username	Problem	Language	Result	Execution time	Memory
123813		MAMBA	Robots (IOI13_robots)	C++17	100 / 100	1906 ms	18424 KiB

robots

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

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
typedef pair<int , int> pii;

const int MAXN = 1e6 + 10;

int a[MAXN], w[MAXN], s[MAXN], x[MAXN], y[MAXN], fA , fB, t;

int arr[MAXN], rtp;

inline void  push(int v) {
	arr[++rtp] = v;
	int id = rtp;
	while (id > 1 && arr[id >> 1] < arr[id]) {
		swap(arr[id] , arr[id >> 1]);
		id >>= 1;
	}
}

inline void pop() {
	if (rtp == 1) return rtp = 0, void();
	swap(arr[1] , arr[rtp--]);
	int id = 1;
	while (true) {
		if ((id << 1) > rtp) return;
		if ((id << 1) == rtp) {
			if (arr[id] < arr[id << 1])
				swap(arr[id] , arr[id << 1]);
			return;
		}
		int me = id << 1;
		if (arr[me] < arr[me + 1])
			me++;
		if (arr[id] < arr[me]) {
			swap(arr[id] , arr[me]);
			id = me;
		}
		else return;
	}
}

inline bool check(int mid) {
	rtp = 0;
	int ptr = 0;
	rep(i , 0 , fA) {
		while (ptr < t && w[a[ptr]] < x[i]) 
			push(s[a[ptr++]]);
		rep(j , 0 , mid) {
			if (rtp) 
				pop();
			else break;
		}
	}
	while (ptr < t)
		push(s[a[ptr++]]);
	rep(i , 0 , fB)
		rep(j , 0 , mid) {
			if (rtp && arr[1] >= y[i]) return false;
			if (rtp) pop();
			else break;
		}
	return !rtp;

}

bool cmp(int l , int r) { return pii(w[l] , s[l]) < pii(w[r] , s[r]); }

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {

	fA = A, fB = B,t = T;

	iota(a , a + T , 0);

	rep(i , 0 , T) w[i] = W[i], s[i] = S[i];
	rep(i , 0 , A) x[i] = X[i];
	rep(i , 0 , B) y[i] = Y[i];

	sort(a , a + T, cmp);

	if (A) sort(x , x + A);
	if (B) sort(y , y + B, greater<int>());

	long long lo = -1, hi = T + 1;
	while (lo != hi - 1) {
		int mid = lo + hi >> 1;

		if (check(mid))
			hi = mid;
		else 
			lo = mid;
	}
	if (hi == T + 1) hi = -1;
	return hi;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:89:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = lo + hi >> 1;
             ~~~^~~~

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