Submission #74441

#	Time	Username	Problem	Language	Result	Execution time	Memory
74441		szawinis	Triangles (CEOI18_tri)	C++17	100 / 100	47 ms	2728 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
#define long long long
using namespace std;

int n;
vector<int> up, down, up_hull, down_hull, ans;
int main() {
	n = get_n();
	for(int i = 3; i <= n; i++) {
		if(is_clockwise(1, 2, i)) down.push_back(i);
		else up.push_back(i);
	}
	up.push_back(2);
	down.push_back(2);
	stable_sort(up.begin(), up.end(), [] (int j, int k) { return is_clockwise(1, j, k); });
	stable_sort(down.begin(), down.end(), [] (int j, int k) { return !is_clockwise(1, j, k); });
	if(up.size() > 1) {
		up_hull.push_back(1);
		up_hull.push_back(up[0]);
		for(int i = 1; i < up.size(); i++) {
			while(up_hull.size() >= 2 && !is_clockwise(up_hull[up_hull.size()-2], up_hull[up_hull.size()-1], up[i]))
				up_hull.pop_back();
			up_hull.push_back(up[i]);
		}
	}
	if(down.size() > 1) {
		down_hull.push_back(1);
		down_hull.push_back(down[0]);
		for(int i = 1; i < down.size(); i++) {
			while(down_hull.size() >= 2 && is_clockwise(down_hull[down_hull.size()-2], down_hull[down_hull.size()-1], down[i]))
				down_hull.pop_back();
			down_hull.push_back(down[i]);
		}
	}

	if(!down_hull.empty() && !up_hull.empty()) {
		if(down_hull[0] == 1 && up_hull[0] == 1) down_hull.erase(down_hull.begin());
		if(down_hull.back() == 2 && up_hull.back() == 2) down_hull.pop_back();
	}
	reverse(down_hull.begin(), down_hull.end());
	vector<int> res = up_hull;
	for(int i: down_hull) res.push_back(i);
	vector<int> ans;
	ans.push_back(res[0]);
	ans.push_back(res[1]);
	for(int i = 2; i < res.size(); i++) {
		while(ans.size() >= 2 && !is_clockwise(ans[ans.size()-2], ans[ans.size()-1], res[i]))
			ans.pop_back();
		ans.push_back(res[i]);
	}

	deque<int> ans_dq;
	for(int i: ans) ans_dq.push_back(i);
	while(ans.size() >= 3) {
		bool found = false;
		int x = ans_dq.front();
		ans_dq.pop_front();
		if(is_clockwise(ans_dq.back(), x, ans_dq.front())) ans_dq.push_front(x);
		else found = true;
		
		x = ans_dq.back();
		ans_dq.pop_back();
		if(is_clockwise(ans_dq.back(), x, ans_dq.front())) ans_dq.push_back(x);
		else found = true;

		if(!found) break;
	}

	give_answer(ans_dq.size());
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < up.size(); i++) {
                  ~~^~~~~~~~~~~
tri.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < down.size(); i++) {
                  ~~^~~~~~~~~~~~~
tri.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 2; i < res.size(); i++) {
                 ~~^~~~~~~~~~~~

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