Submission #404696

#	Time	Username	Problem	Language	Result	Execution time	Memory
404696		Kenzo_1114	Robots (IOI13_robots)	C++17	0 / 100	4 ms	332 KiB

robots

#include<bits/stdc++.h>
#include "robots.h"
using namespace std;
const int MAXN = 100010;
const int MAXT = 1000010;

int a, b, n, x[MAXN], y[MAXN], w[MAXT], s[MAXT];

bool valid(int Minutes)
{
	vector<pair<int, int> > p;
	for(int i = 0; i < n; i++) p.push_back({w[i], i});
	sort(p.begin(), p.end());
		
	int id = 0;
	set<pair<int, int> > xs, ys;
	set<pair<int, int> > :: iterator it;
	for(int i = 0; i < (int) p.size(); i++)
	{
		int xcur = p[i].first;
		int j = p[i].second;
		int ycur = s[j];

		while(id < a && xcur > x[id])
		{
			for(int k = 0; k < Minutes; k++)
				if(!ys.empty())
					ys.erase(*(--ys.end()));
			id++;
		}

		ys.insert({ycur, j});
	}

	while(id < a)
	{
		for(int k = 0; k < Minutes; k++)
			if(!ys.empty())
				ys.erase(*(--ys.end()));
		id++;
	}

	p.clear();
	for(it = ys.begin(); it != ys.end(); it++)
		p.push_back(*it);

	id = 0;
	for(int i = 0; i < (int) p.size(); i++)
	{
		int ycur = p[i].first;
		int j = p[i].second;
		int xcur = w[j];

		while(id < b && ycur > y[id])
		{
			for(int k = 0; k < Minutes; k++)
				if(!xs.empty())
					xs.erase(*(--xs.end()));
			id++;
		}

		xs.insert({xcur, j});
	}

	while(id < b)
	{
		for(int k = 0; k < Minutes; k++)
			if(!xs.empty())
				xs.erase(*(--xs.end()));
		id++;
	}

	if(xs.empty())	return true;
	return false;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
	a = A, b = B, n = T;

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

	sort(x, x + A);
	sort(y, y + B);

	int bg = 0, ed = MAXT;

	while(bg < ed)
	{
		int mid = (bg == ed - 1) ? bg : (bg + ed) >> 1;

		if(valid(mid))	ed = mid;
		else	bg = mid + 1;
	}

	return (bg == MAXT) ? -1 : bg;
}

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