Submission #1143094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143094		fabijan_cikac	Triangles (CEOI18_tri)	C++20	100 / 100	20 ms	3596 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"

using namespace std;

#define pb push_back

/*int get_n(){
	int n; cin >> n; return n;
}*/

/*bool is_clockwise(int x, int y, int z){
	cout << "?? " << x << ' ' << y << ' ' << z << endl;
	bool b; cin >> b; return b;
}*/

bool ccw(int x, int y, int z){
	return is_clockwise(x, y, z);
}

/*void give_answer(int x){
	cout << x << endl;
}*/

int n, a, b;

bool cmp(int x, int y){
	if (x == y) return 0;
	return !ccw(a, x, y);
}

int main(){
	n = get_n();
	a = n - 1, b = n;
	
	vector<int> v[2];
	for (int i = 1; i <= n - 2; ++i)
		v[!ccw(a, b, i)].pb(i);
	for (int i = 0; i < 2; ++i){
		sort(v[i].begin(), v[i].end(), cmp);
		v[i].pb(b), swap(a, b);
	}
	
	/*for (int x: v[0])
		cout << x << ' ';
	cout << endl;
	for (int x: v[1])
		cout << x << ' ';
	cout << endl;*/
		
	vector<int> c[2];
	for (int i = 0; i < 2; ++i){
		c[i].pb(a);
		for (int x: v[i]){
			while ((int)(c[i].size()) >= 2 && ccw(c[i][(int)(c[i].size()) - 2], c[i].back(), x))
				c[i].pop_back();
			c[i].pb(x);
		}
		swap(a, b);
	}
	
	/*for (int x: c[0])
		cout << x << ' ';
	cout << endl;
	for (int x: c[1])
		cout << x << ' ';
	cout << endl;*/
	
	if ((int)(c[0].size()) == 2 || (int)(c[1].size()) == 2){
		give_answer((int)(c[0].size()) + (int)(c[1].size()) - 2); return 0;
	}
	
	int l1 = 0, r1 = (int)(c[1].size()) - 2;
	int l2 = (int)(c[0].size()) - 2, r2 = 0;
	
	while (1){
		if (ccw(c[1][r1], c[0][l1], c[0][l1 + 1])) ++l1;
		else if (ccw(c[1][r1 - 1], c[1][r1], c[0][l1])) --r1;
		else break;
	}
	
	while (1){
		if (ccw(c[0][l2], c[1][r2], c[1][r2 + 1])) ++r2;
		else if (ccw(c[0][l2 - 1], c[0][l2], c[1][r2])) --l2;
		else break;
	}
	
	set<int> s;
	for (int i = l1; i <= l2; ++i)
		s.insert(c[0][i]);
	for (int i = r2; i <= r1; ++i)
		s.insert(c[1][i]);

	give_answer((int)(s.size()));

	return 0;
}

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