제출 #886747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886747		byakko	로봇 (IOI13_robots)	C++17	28 / 100	137 ms	15456 KiB

robots

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

const int INF = 2e9;

bool win(array<int, 2> robot, array<int, 2> toy) {
	return robot[0] > toy[0] and robot[1] > toy[1];
}

bool check(int X[], int A, int W[], int T, int k) {
	int cur = 0;
	for(int i = 0; i < T; i += k) {
		int end = min(T, i + k);
		for(int j = i; j < end; j++)
			if(X[cur] <= W[j]) return false;
		cur++;
	}
	return true;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	if(T == 2) {
		vector<array<int, 2>> robot;
		for(int i = 0; i < A; i++) {
			robot.push_back({X[i], INF});
		}
		for(int i = 0; i < B; i++) {
			robot.push_back({INF, Y[i]});
		}

		vector<array<int, 2>> toy;
		for(int i =0 ; i < T; i++) {
			toy.push_back({W[i], S[i]});
		}

		for(int _ = 0; _ < 2; _++) {
			bool ok = true;
			for(int j = 0; j < T; j++) {
				if(!win(robot[j], toy[j])) 
					ok = false;
			}
			if(ok) return 1;
			reverse(robot.begin(), robot.end());
		}

		bool ok = true;
		for(int i = 0; i < T; i++) {
			bool found = false;
			for(auto r: robot) if(win(r, toy[i])) {
				found = true;
				break;
			}
			if(!found) {
				ok = false;
				break;
			}
		}

		if(ok) return T;
		return -1;
	} else {
		sort(X, X + A);
		reverse(X, X + A);
		sort(W, W + T);
		reverse(W, W + T);
		if(!check(X, A, W, T, T)) return -1;
		int lo = 0, hi = T;
		while(lo + 1 < hi) {
			int mid = (lo + hi) >> 1;
			if(check(X, A, W, T, mid)) hi = mid;
			else lo = mid;
		}
		return hi;
	}
}

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