Submission #990988

#	Time	Username	Problem	Language	Result	Execution time	Memory
990988		starchan	Triangles (CEOI18_tri)	C++17	0 / 100	1 ms	348 KiB

tri

#include<bits/stdc++.h>

#include "trilib.h"

using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back

/*bool is_clockwise(int i, int j, int k)
{
	cout << "Are the vertices numbered " << i << " " << j << " " << k << " clockwise in this order?" << endl;
	string ret; cin >> ret;
	return (ret[0] == 'y' || ret[0] == 'Y');
}*/

vector<int> solve(int n)
{
	if(n == 3)
	{
		if(is_clockwise(1, 2, 3))
			return {1, 2, 3};
		else
			return {3, 2, 1};
	}
	vector<int> v = solve(n-1);
	int K = v.size();
	//v[0], v[1], ..., v[]
	int md = is_clockwise(v[0], v[1], n);
	int l = 0; int r = K-1; int p = -1;//non MD element.
	while(l < r)
	{
		if((r-l+1) <= 6)
		{
			while((l < r) && (is_clockwise(v[l], v[(l+1)%K], n) == md))
				l++;
			while((r > l) && (is_clockwise(v[r], v[(r+1)%K], n) == md))
				r--;
			if((l == r) && (is_clockwise(v[l], v[(l+1)%K], n) == md))
				return v;
			vector<int> c; c.pb(n);
			if(md == 1)
			{
				int u = (r+1)%K; if(l < u) l+=K;
				for(int t = u; t <= l; t++)
					c.pb(v[t%K]);
				return c;
			}
			else
			{
				int u = l; r = (r+1)%K; if(r < u) r+=K;
				for(int t = u; t <= r; t++)
					c.pb(v[t%K]);
			}
			return c;
		}
		int a = (2*l+r)/3; int b = (2*r+l)/3;
		//[l,   a,    b,   r]
		if(is_clockwise(v[a], v[(a+1)%K], n) != md)
		{
			p = a;
			break;
		}
		if(is_clockwise(v[b], v[(b+1)%K], n) != md)
		{
			p = b;
			break;
		}
		l = a; r = b;
	}
	int L1 = 0;
	int R1 = p;//first non md.
	while(L1 < R1)
	{
		int m = (L1+R1)/2;
		if(is_clockwise(v[m], v[(m+1)%K], n) != md)
			R1 = m;
		else
			L1 = m+1;	
	}
	int L2 = p+1;
	int R2 = K;//first md.
	while(L2 < R2)
	{
		int m = (L2+R2)/2;
		if(is_clockwise(v[m], v[(m+1)%K], n) == md)
			R2 = m;
		else
			L2 = m+1;
	}
	//L1, ..., R2 consists of non mds.
	if(md == 0)
		swap(L1, R2);
	//1...L1 --> n --> R2 -->
	vector<int> c; c.pb(n);
	if(L1 < R2)
		L1+=K;
	for(int j = R2; j <= L1; j++)
		c.pb(v[j%K]);
	return c;
}

signed main()
{
	/*int n; cin >> n;
	vector<int> vv = solve(n);
	cout << "Convex hull = " << endl;
	for(auto tt: vv)
		cout << tt << " ";
	cout << endl;*/
	give_answer(solve(get_n()).size());
	return 0;
}

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