Submission #367879

#	Time	Username	Problem	Language	Result	Execution time	Memory
367879		ogibogi2004	Triangles (CEOI18_tri)	C++14	100 / 100	28 ms	2176 KiB

tri

#include<bits/stdc++.h>
#include "trilib.h"
using namespace std;
#define ll long long
ll n;
int t;
bool cmp1(int x,int y)
{
	return is_clockwise(x,y,t);
}
bool cmp2(int x,int y)
{
	return is_clockwise(x,t,y);
}
int main()
{
	n=get_n();
	vector<int>v1,v2;
	for(int i=3;i<=n;i++)
	{
		if(is_clockwise(1,2,i))
		{
			v2.push_back(i);
		}
		else
		{
			v1.push_back(i);
		}
	}
	t=2;
	sort(v1.begin(),v1.end(),cmp1);
	v1.push_back(2);
	reverse(v1.begin(),v1.end());
	v1.push_back(1);
	reverse(v1.begin(),v1.end());
	sort(v2.begin(),v2.end(),cmp2);
	deque<int>UH,LH;
	UH.push_back(v1[0]);
	for(int i=1;i<v1.size();i++)
	{
		while(UH.size()>=2&&!is_clockwise(UH.end()[-2],UH.end()[-1],v1[i]))
		{
			UH.pop_back();
		}
		UH.push_back(v1[i]);
	}
	if(v2.size()>0)
	{
		LH.push_back(v2[0]);
	}
	for(int i=1;i<v2.size();i++)
	{
		while(LH.size()>=2&&is_clockwise(LH.end()[-2],LH.end()[-1],v2[i]))
		{
			LH.pop_back();
		}
		LH.push_back(v2[i]);
	}
	while(UH.size()>0&&LH.size()>0&&UH.size()+LH.size()>3)
	{
		if(UH.size()>1)
		{
			if(is_clockwise(UH[1],UH[0],LH[0]))
			{
				UH.pop_front();
				continue;
			}
			if(!is_clockwise(UH.end()[-2],UH.end()[-1],LH.back()))
			{
				UH.pop_back();
				continue;
			}
		}
		if(LH.size()>1)
		{
			if(!is_clockwise(LH[1],LH[0],UH[0]))
			{
				LH.pop_front();
				continue;
			}
			if(is_clockwise(LH.end()[-2],LH.end()[-1],UH.back()))
			{
				LH.pop_back();
				continue;
			}
		}
		break;
	}
	give_answer(UH.size()+LH.size());
return 0;
}
/*
6
2 2
3 2
1 4
4 3
1 1
5 1
*/

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=1;i<v1.size();i++)
      |              ~^~~~~~~~~~
tri.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=1;i<v2.size();i++)
      |              ~^~~~~~~~~~

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