Submission #128413

#	Time	Username	Problem	Language	Result	Execution time	Memory
128413		TadijaSebez	Triangles (CEOI18_tri)	C++11	75 / 100	31 ms	2292 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 in[N];
int nxt[N],pre[N];
vector<int> Merge(vector<int> x, vector<int> y)
{
	vector<int> z;
	if(x[1]==2) swap(x,y);
	for(int i:x) z.pb(i);
	for(int i=2;i<y.size();i++) z.pb(y[i]);
	for(int i=1;i<z.size();i++)
	{
		nxt[z[i-1]]=z[i];
		pre[z[i]]=z[i-1];
	}
	pre[z[0]]=z.back();
	nxt[z.back()]=z[0];
	in[1]=in[2]=1;
	queue<int> q;
	q.push(1);
	q.push(2);
	while(q.size())
	{
		int i=q.front();
		q.pop();
		in[i]=0;
		int l=pre[i],r=nxt[i];
		if(is_clockwise(i,r,l))
		{
			nxt[i]=pre[i]=0;
			nxt[l]=r;
			pre[r]=l;
			if(!in[l]) q.push(l),in[l]=1;
			if(!in[r]) q.push(r),in[r]=1;
		}
	}
	int st=0;
	for(int i=0;i<N;i++) if(nxt[i]){ st=i;break;}
	vector<int> ans;
	int i=st;
	do
	{
		ans.pb(i);
		i=nxt[i];
	}while(i!=st);
	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;
}

Compilation message (stderr)

tri.cpp: In function 'std::vector<int> Merge(std::vector<int>, std::vector<int>)':
tri.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=2;i<y.size();i++) z.pb(y[i]);
              ~^~~~~~~~~
tri.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<z.size();i++)
              ~^~~~~~~~~

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