Submission #73603

#	Time	Username	Problem	Language	Result	Execution time	Memory
73603		zscoder	Triangles (CEOI18_tri)	C++17	100 / 100	45 ms	2208 KiB

tri

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "trilib.h"

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int nn; int god;
bool is_cl(int x, int y, int z)
{
	return is_clockwise(x+1,y+1,z+1);
}
bool cmp(int x, int y)
{
	return !is_cl(god,x,y);
}
int ans;

vector<int> ez_convex_hull(vector<int> vec)
{
	vector<int> S;
	for(int i=0;i<vec.size();i++)
	{
		int u=vec[i];
		while(S.size()>=2&&is_cl(S[int(S.size())-2], S[int(S.size())-1], u))
		{
			S.pop_back();
		}
		S.pb(u);
	}
	return S;
}

int main()
{
	nn = get_n();
	vi U, D; god=0;
	for(int i=2;i<nn;i++)
	{
		if(is_cl(0,1,i))
		{
			U.pb(i);
		}
		else
		{
			D.pb(i);
		}
	}
	stable_sort(U.begin(),U.end(),cmp);
	stable_sort(D.begin(),D.end(),cmp);
	D.pb(0); U.pb(1);
	/*
	for(int x:U)
	{
		cerr<<x<<' ';
	}
	cerr<<'\n';
	for(int x:D)
	{
		cerr<<x<<' ';
	}
	cerr<<'\n';
	*/
	U = ez_convex_hull(U); D = ez_convex_hull(D);
	vector<int> combined;
	for(int v:U) combined.pb(v);
	for(int v:D) combined.pb(v);
	/*
	for(int v:combined) 
	{
		cerr<<v<<' ';
	}
	cerr<<'\n';
	*/
	combined = ez_convex_hull(combined);
	deque<int> dq;
	for(int v:combined) 
	{
		dq.pb(v);
	}
	while(1)
	{
		bool quit=1;
		int x = dq.back(); dq.pop_back();
		if(is_cl(dq.back(), x, dq.front()))
		{
			quit=0;
		}
		else dq.pb(x);
		x = dq.front(); dq.pop_front();
		if(!is_cl(dq.front(), x, dq.back()))
		{
			quit=0;
		}
		else dq.push_front(x);
		if(quit) break;
	}
	give_answer(dq.size());
}

Compilation message (stderr)

tri.cpp: In function 'std::vector<int> ez_convex_hull(std::vector<int>)':
tri.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~

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