Submission #707147

#	Time	Username	Problem	Language	Result	Execution time	Memory
707147		Nonoze	Robots (IOI13_robots)	C++14	100 / 100	1591 ms	28416 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

int egal0(int N, int A, int W[], int X[]) {
	int compmax=0;
	sort(W, W+N);
	int j=A;
	int cnt[A];
	for (int i = 0; i < A; ++i)
	{
		cnt[i]=0;
	}
	for (int i = N-1; i >= 0; --i)
	{
		int x=j;
		while (j>0 && X[j-1]>=W[i]) j--;
		if (x!=j) {
			cnt[j]++;
			compmax=max(compmax, 1);
		} else {
			int mincomp=INT_MAX, empl=-1;
			for (int k = j; k < A; ++k)
			{
				if (mincomp>cnt[k])
				{
					mincomp=cnt[k];
					empl=k;
				}
			}
			cnt[empl]++;
			compmax=max(compmax, cnt[empl]);
		}
	}
	return compmax;
}

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

	if (A!=0) sort(X, X+A);
	if (B!=0) sort(Y, Y+B);
	int maxa=((A!=0)?X[A-1]:0), maxb=((B!=0)?Y[B-1]:0);
	vector<pair<int, int>> paires;
	for (int i = 0; i < N; ++i) {
		if (W[i]>=maxa && S[i]>=maxb) return -1;
		paires.push_back({W[i], S[i]});
	}
	sort(paires.begin(), paires.end());

	#define int long long

	int l=0, r=N;
	while (l<r) {
		int mid=(l+r) / 2;

		priority_queue<int> prio;
		int cnt=0;
		for (int i = 0; i < A; ++i)
		{
			while (cnt < N && paires[cnt].first < X[i])
			{
				prio.push(paires[cnt].second);
				cnt++;
			}
			int midtemp=0;
			while (midtemp<mid && !prio.empty()) {
				prio.pop();
				midtemp++;
			}
		}

		for (int i = cnt; i < N; ++i)
		{
			prio.push(paires[i].second);
		}

		cnt=0;
		for (int i = B-1; i >= 0; --i)
		{
			int x=prio.top(), midtemp=0;
			while (midtemp<mid && !prio.empty() && x < Y[i]) {
				prio.pop();
				midtemp++;
				x=prio.top();
			}
		}

		if (!prio.empty()) {
			l=mid+1;
		} else {
			r=mid;
		}

	}

	#undef int
	return l;
}

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