Submission #918161

#	Time	Username	Problem	Language	Result	Execution time	Memory
918161		NK_	Triangles (CEOI18_tri)	C++17	100 / 100	19 ms	2800 KiB

tri

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "trilib.h"
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
 
mt19937 rng(1008);
 
// g++-13 -O2 trilib.cpp A.cpp -std=c++17 -o ./G
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N = get_n();
 
	vi L = {1}, R;
	for(int i = 2; i < N; i++) {
		if (!is_clockwise(1, 2, i + 1)) L.pb(i);
		else R.pb(i);
	}

	sort(begin(L), end(L), [&](int x, int y) {
		return is_clockwise(1, x + 1, y + 1);
	});	

	sort(begin(R), end(R), [&](int x, int y) {
		return is_clockwise(1, x + 1, y + 1);
	});	
 		
 	L.insert(begin(L), 0);

 	// for(auto& x : L) cout << x << " ";
 	// cout << endl;

 	// for(auto& x : R) cout << x << " ";
 	// cout << endl;

	auto fix = [&](vi A) {
		vi C;
		for(int i = 0; i < sz(A); i++) {
			while(sz(C) >= 2 && !is_clockwise(C[sz(C) - 2] + 1, C[sz(C) - 1] + 1, A[i] + 1)) C.pop_back();
			C.pb(A[i]);
		}
 
		return C;
	};
 
	L = fix(L); R = fix(R);
	vi C = L; C.insert(end(C), begin(R), end(R));
	C = fix(C);

	// for(auto& x : C) cout << x << " ";
 	// cout << endl;

	deque<int> D(begin(C), end(C));

	while(1) {
			
		bool done = 1;

		int x = D.back(); D.pop_back();
		if (!is_clockwise(D.back() + 1, x + 1, D.front() + 1)) done = 0;
		else D.pb(x);

		int y = D.front(); D.pop_front();
		if (!is_clockwise(D.back() + 1, y + 1, D.front() + 1)) done = 0;
		else D.push_front(y);

		if (done) break;
	}

	// for(auto& x : D) cout << x << " ";
	// cout << endl;
 
	give_answer(sz(D));
 
	exit(0-0);
}

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