Submission #1173546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173546		sleepntsheep	Triangles (CEOI18_tri)	C++20	100 / 100	14 ms	1352 KiB

tri

#include <stdio.h>
#include <algorithm>
#include "trilib.h"
#include <string.h>
#include <stdlib.h>
#include <deque>

int main() {
	std::deque<int>L,R,ll,rr;

	int n = get_n();

	for(int i=3;i<=n;++i)
		if(is_clockwise(1,2,i))R.push_back(i);
		else L.push_back(i);

	std::sort(R.begin(),R.end(),[](int i,int j){ return is_clockwise(1,i,j); });
	std::sort(L.begin(),L.end(),[](int i,int j){ return is_clockwise(1,i,j); });
	rr={2};
	ll={1};
	for(auto i:R){
		while(rr.size()>1&&!is_clockwise(rr[rr.size()-2],rr.back(),i))rr.pop_back();
		rr.push_back(i);
	}
	for(auto i:L){
		while(ll.size()>1&&!is_clockwise(ll[ll.size()-2],ll.back(),i))ll.pop_back();
		ll.push_back(i);
	}

	while(1){
		int f=0;
		while(rr.size()>=2&&ll.size()>=1&&!is_clockwise(ll.back(),rr[0],rr[1]))rr.pop_front(),++f;
		while(rr.size()>=1&&ll.size()>=2&&!is_clockwise(ll[ll.size()-2],ll.back(),rr[0]))ll.pop_back(),++f;
		while(rr.size()>=2&&ll.size()>=1&&!is_clockwise(rr[rr.size()-2],rr.back(),ll[0]))rr.pop_back(),++f;
		while(rr.size()>=1&&ll.size()>=2&&!is_clockwise(rr.back(),ll[0],ll[1]))ll.pop_front(),++f;
		if(!f)break;
	}

	give_answer(ll.size()+rr.size());
}

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