Submission #641899

#	Time	Username	Problem	Language	Result	Execution time	Memory
641899		ymm	로봇 (IOI13_robots)	C++17	0 / 100	3033 ms	40000 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;
const int N = 1'000'010;

bool bintry(int cnt, int a, int b, int t, int x[], int y[], int w[], int s[])
{
	static pii toys[N];
	Loop (i,0,t)
		toys[i] = {w[i], s[i]};
	sort(toys, toys+t);
	sort(x, x+a);
	sort(y, y+b);
	multiset<int, greater<int>> by_s;
	int i, j;
	for (i=0,j=0; i < a; ++i) {
		while (j < t && w[j] < x[i]) {
			by_s.insert(s[j]);
			++j;
		}
		for (int _=0; _<cnt && by_s.size(); ++_)
			by_s.erase(by_s.begin());
	}
	for (; j < t; ++j)
		by_s.insert(s[j]);
	for (i=b-1; i>=0; --i) {
		if (by_s.size() && *by_s.begin() >= y[i])
			return 0;
		for (int _=0; _<cnt && by_s.size(); ++_)
			by_s.erase(by_s.begin());
	}
	if (by_s.size())
		return 0;
	return 1;
}

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[])
{
	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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10