Submission #128406

#	Time	Username	Problem	Language	Result	Execution time	Memory
128406		TadijaSebez	Triangles (CEOI18_tri)	C++11	0 / 100	2 ms	376 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,y,x);});
	vector<int> ans;
	ans.pb(1);
	for(int i:v)
	{
		while(ans.size()>1 && is_clockwise(ans[ans.size()-2],ans.back(),i)) ans.pop_back();
		ans.pb(i);
	}
	return ans;
}
const int N=40050;
bool ban[N];
vector<int> Merge(vector<int> x, vector<int> y)
{
	for(int i=0;i<N;i++) ban[i]=1;
	for(int i:x) ban[i]=0;
	for(int i:y) ban[i]=0;
	int t;
	if(y[1]==2) reverse(y.begin()+1,y.end()),t=1;
	else reverse(x.begin()+1,x.end()),t=0;
	x.pop_back();
	while(1)
	{
		if(y.size()>2 && is_clockwise(x.back(),y.back(),y[y.size()-2])==t) ban[y.back()]=1,y.pop_back();
		else if(x.size()>1 && is_clockwise(y.back(),x.back(),x[x.size()-2])!=t) ban[x.back()]=1,x.pop_back();
		else break;
	}
	reverse(x.begin(),x.end());
	reverse(y.begin(),y.end());
	y.pop_back();
	t^=1;
	while(1)
	{
		if(y.size()>1 && is_clockwise(x.back(),y.back(),y[y.size()-2])==t) ban[y.back()]=1,y.pop_back();
		else if(x.size()>2 && is_clockwise(y.back(),x.back(),x[x.size()-2])!=t) ban[x.back()]=1,x.pop_back();
		else break;
	}
	vector<int> ans;
	for(int i=0;i<N;i++) if(!ban[i]) ans.pb(i);
	return ans;
}
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);
	if(v[0].empty() || v[1].empty())
	{
		if(v[0].empty()) v[0]=v[1];
		v[0].pb(2);
		v[0]=Hull(v[0]);
		give_answer(v[0].size());
		return 0;
	}
	v[0].pb(2);
	v[1].pb(2);
	v[0]=Hull(v[0]);
	v[1]=Hull(v[1]);
	vector<int> all=Merge(v[0],v[1]);
	give_answer(all.size());
	return 0;
}

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