Submission #128427

#	Time	Username	Problem	Language	Result	Execution time	Memory
128427		TadijaSebez	Triangles (CEOI18_tri)	C++11	75 / 100	32 ms	1652 KiB

tri

#include "trilib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> Hull(vector<int> v)
{
	sort(v.begin(),v.end(),[&](int x, int y){ return is_clockwise(1,x,y);});
	vector<int> ans;
	for(int i:v)
	{
		while(ans.size()>1 && !is_clockwise(ans[ans.size()-2],ans.back(),i)) ans.pop_back();
		ans.pb(i);
	}
	ans.insert(ans.begin(),1);
	return ans;
}
const int N=40050;
bool in[N];
int nxt[N],pre[N];
void Merge(vector<int> x, vector<int> y)
{
	for(int t=0;t<2;t++)
	{
		x.pop_back();
		while(1)
		{
			bool ok=0;
			int sz=x.size();
			if(sz>1 && !is_clockwise(x[sz-2],x[sz-1],y.back())) x.pop_back(),ok=1;
			sz=y.size();
			if(sz>1 && !is_clockwise(x.back(),y[sz-1],y[sz-2])) y.pop_back(),ok=1;
			if(!ok) break;
		}
		reverse(x.begin(),x.end());
		reverse(y.begin(),y.end());
		swap(x,y);
	}
	give_answer(x.size()+y.size());
}
int main()
{
	int n=get_n();
	vector<int> v[2];
	for(int i=3;i<=n;i++) v[is_clockwise(1,2,i)].pb(i);
	v[0].pb(2);
	v[1].pb(2);
	v[0]=Hull(v[0]);
	v[1]=Hull(v[1]);
	if(min(v[0].size(),v[1].size())==2)
	{
		give_answer(max((int)v[0].size(),(int)v[1].size()));
		return 0;
	}
	reverse(v[1].begin()+1,v[1].end());
	Merge(v[0],v[1]);
	return 0;
}

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