Submission #78952

#	Time	Username	Problem	Language	Result	Execution time	Memory
78952		aminra	Triangles (CEOI18_tri)	C++14	100 / 100	43 ms	25252 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)107;
const int infint = (int)1e9;
int n;
vector<int> u, d, ans;
/*int get_n()
{
	int x;
	cin >> x;
	return x;
}
int is_clockwise(int x, int y, int z)
{
	cout << x << " " << y << " " << z << endl;
	int ans;
	cin >> ans;
	return ans;
}
void give_answer(int t)
{
	cout << t << endl;
	return;
}*/
bool cw(int i, int j)
{
	return is_clockwise(1, i, j);
}
bool ccw(int i, int j)
{
	return !is_clockwise(1, i, j);
}
vector<int> convex(vector<int> v)
{
	vector<int> ans;
	for (auto u : v)
	{
		while(ans.size() >= 2 && is_clockwise(ans[ans.size() - 2], ans.back(), u))
			ans.pop_back();
		ans.push_back(u);
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	n = get_n();
	for (int i = 3; i <= n; i++)
		if(is_clockwise(1, 2, i))
			d.push_back(i);
		else
			u.push_back(i);
			
	sort(d.begin(), d.end(), ccw);
	sort(u.begin(), u.end(), ccw);
	d.push_back(2);
	u.push_back(1);
	
	d = convex(d), u = convex(u);
	for (auto x : d)
		ans.push_back(x);
	for (auto x : u)
		ans.push_back(x);
	/*for (auto x : ans)
		cout << x << " ";
	cout << endl;
	ans = convex(ans);
	for (auto x : ans)
		cout << x << " ";
	cout << endl;*/
	ans = convex(ans);
	
	
	deque<int> qs;
	for (auto x : ans)
		qs.push_back(x);
	bool did = false;
	while(!did)
	{
		did = 1;
		int a = qs.back(); qs.pop_back();
		if(is_clockwise(qs.back(), a, qs.front()))
			did = 0;
		else
			qs.push_back(a);
		a = qs.front();
		qs.pop_front();
		if(!is_clockwise(qs.front(), a, qs.back()))
			did = 0;
		else
			qs.push_front(a);
	}
	give_answer(qs.size());
}

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