Submission #762276

#	Time	Username	Problem	Language	Result	Execution time	Memory
762276		SanguineChameleon	Robots (IOI13_robots)	C++17	90 / 100	3059 ms	28296 KiB

robots

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

const int maxN = 1e6 + 20;
pair<int, int> W[maxN];
pair<int, int> S[maxN];
pair<int, int> cnt[maxN];
long long sum[maxN];
int A, B, N;

bool check(int K) {
	for (int i = 0; i <= B; i++) {
		sum[i] = -1LL * i * K; 
	}
	for (int i = 0; i < N; i++) {
		long long lim = 1LL * cnt[i].first * K;
		for (int j = cnt[i].second; j <= B; j++) {
			sum[j]++;
			if (sum[j] > lim) {
				return false;
			}
		}
	}
	return true;
}

int putaway(int _A, int _B, int _N, int X[], int Y[], int _W[], int _S[]) {
	A = _A;
	B = _B;
	N = _N;
	for (int i = 0; i < N; i++) {
		W[i].first = _W[i];
		W[i].second = i;
	}
	for (int i = 0; i < N; i++) {
		S[i].first = _S[i];
		S[i].second = i;
	}
	sort(W, W + N, greater<pair<int, int>>());
	sort(S, S + N, greater<pair<int, int>>());
	sort(X, X + A, greater<int>());
	sort(Y, Y + B, greater<int>());
	int lt = -1;
	for (int i = 0; i < N; i++) {
		while (lt < N - 1 && X[lt + 1] > W[i].first) {
			lt++;
		}
		cnt[W[i].second].first = lt + 1;
	}
	lt = -1;
	for (int i = 0; i < N; i++) {
		while (lt < N - 1 && Y[lt + 1] > S[i].first) {
			lt++;
		}
		cnt[S[i].second].second = lt + 1;
	}
	if (A < B) {
		for (int i = 0; i < N; i++) {
			swap(cnt[i].first, cnt[i].second);
		}
		swap(A, B);
	}
	sort(cnt, cnt + N);
	lt = 1;
	int rt = N;
	int res = -1;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		if (check(mt)) {
			res = mt;
			rt = mt - 1;
		}
		else {
			lt = mt + 1;
		}
	}
	return res;
}

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