Submission #886745

#	Time	Username	Problem	Language	Result	Execution time	Memory
886745		byakko	Robots (IOI13_robots)	C++17	14 / 100	95 ms	20192 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];
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	assert(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;

	/*
	set<int> St;
	for(int i = 0; i < T; i++)
		St.insert(W[i]);
	sort(X, X + A);
	int cont = 0;
	bool ok = true;
	while(!St.empty()) {
		bool deletes = false;
		for(int i = 0; i < A; i++) {
			if(St.empty()) break;
			auto it = St.upper_bound(X[i]);
			if(it == St.begin()) continue;
			deletes = true;
			it--;
			St.erase(it);
		}
		if(!deletes) {
			ok = false;
			break;
		}
		cont++;
	}
    return ok ? cont : -1;
	*/
}

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