Submission #641903

#	Time	Username	Problem	Language	Result	Execution time	Memory
641903		ymm	Robots (IOI13_robots)	C++17	100 / 100	1478 ms	24292 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
static const int N = 1'000'010;
static pii toys[N];

bool bintry(int cnt, int a, int b, int t, int x[], int y[], int w[], int s[])
{
	priority_queue<int> by_s;
	int i, j;
	for (i=0,j=0; i < a; ++i) {
		while (j < t && toys[j].first < x[i]) {
			by_s.push(toys[j].second);
			++j;
		}
		for (int _=0; _<cnt && by_s.size(); ++_)
			by_s.pop();
	}
	for (; j < t; ++j)
		by_s.push(toys[j].second);
	for (i=b-1; i>=0; --i) {
		if (by_s.size() && by_s.top() >= y[i])
			return 0;
		for (int _=0; _<cnt && by_s.size(); ++_)
			by_s.pop();
	}
	if (by_s.size())
		return 0;
	return 1;
}

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[])
{
	Loop (i,0,t)
		toys[i] = {w[i], s[i]};
	sort(toys, toys+t);
	sort(x, x+a);
	sort(y, y+b);
	int l = 0, r = t+1;
	while (l < r) {
		int m = (l+r)/2;
		if (bintry(m, a,b,t,x,y,w,s))
			r = m;
		else
			l = m+1;
	}
	return l==t+1?-1:l;
}

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