Submission #299622

#	Time	Username	Problem	Language	Result	Execution time	Memory
299622		Berted	Triangles (CEOI18_tri)	C++14	100 / 100	38 ms	2424 KiB

tri

#include "trilib.h"
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>

using namespace std;

int N;
vector<int> data, p1, p2;

bool comp(const int &l, const int &r)
{
	return !is_clockwise(1, l, r);
}

int main()
{
	N = get_n();
	for (int i = 3; i <= N; i++)
	{
		if (is_clockwise(1, i, 2)) {p2.push_back(i);}
		else {p1.push_back(i);}
	}

	sort(p1.begin(), p1.end(), comp);
	for (auto &x : p1) {data.push_back(x);}
	data.push_back(2);
	sort(p2.begin(), p2.end(), comp);
	for (auto &x : p2) {data.push_back(x);}


	//for (auto &x : data) {cout << x << " ";} cout << "\n";

	deque<int> stack;
	stack.push_back(1);
	for (auto &x : data)
	{
		while (stack.size() > 1 && is_clockwise(stack[stack.size() - 2], stack.back(), x)) {stack.pop_back();}
		stack.push_back(x);
		//cout << "inserted " << x << "\n";
	}

	//for (auto &x : stack) {cout << x << " ";} cout << "\n";

	while (stack.size() > 2)
	{
		if (is_clockwise(stack.front(), stack[1], stack.back())) {stack.pop_front();}
		else if (is_clockwise(stack.back(), stack.front(), stack[stack.size() - 2])) {stack.pop_back();}
		else {break;}
	}

	//for (auto &x : stack) {cout << x << " ";} cout << "\n";

	give_answer(stack.size());
	return 0;
}

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