Submission #229815

#	Time	Username	Problem	Language	Result	Execution time	Memory
229815		dolphingarlic	Triangles (CEOI18_tri)	C++14	100 / 100	36 ms	1576 KiB

tri

#include "trilib.h"

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

bool cmp(int A, int B) { return is_clockwise(1, A, B); }

vector<int> d[2]{{2}, {2}}, h[2];

int main() {
	int n = get_n();
	for (int i = 3; i <= n; i++) d[is_clockwise(1, 2, i)].push_back(i);

	for (int i = 0; i < 2; i++) {
		sort(d[i].begin(), d[i].end(), cmp);
		for (int j : d[i]) {
			while (h[i].size() > 1 && is_clockwise(j, h[i].back(), h[i][h[i].size() - 2]))
				h[i].pop_back();
			h[i].push_back(j);
		}
		if (i) reverse(h[i].begin(), h[i].end());
		h[i].insert(h[i].begin(), 1);
	}

	if (min(h[0].size(), h[1].size()) == 2)
		return give_answer(max(h[0].size(), h[1].size())), 0;

	for (int i = 0; i < 2; i++) {
		h[0].pop_back();

		while (true) {
			if (h[0].size() > 1 && is_clockwise(h[1].back(), h[0].back(), h[0][h[0].size() - 2]))
				h[0].pop_back();
			else if (h[1].size() > 1 && is_clockwise(h[1][h[1].size() - 2], h[1].back(), h[0].back()))
				h[1].pop_back();
			else break;
		}

		swap(h[0], h[1]);
		reverse(h[0].begin(), h[0].end());
		reverse(h[1].begin(), h[1].end());
	}

	give_answer(h[0].size() + h[1].size());
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25