Submission #459272

#	Time	Username	Problem	Language	Result	Execution time	Memory
459272		hhhhaura	Triangles (CEOI18_tri)	C++14	100 / 100	25 ms	1548 KiB

tri

#define wiwihorz
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#include <bits/stdc++.h>
#include "trilib.h"
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define all(x) x.begin(), x.end()
using namespace std;
namespace solver {
	vector<int> v[2], hull;
	void solve() {
		int n = get_n();
		v[0].push_back(1);
		v[1].push_back(2);
		rep(i, 3, n) v[is_clockwise(2, 1, i)].push_back(i);
		rep(i, 0, 1) sort(v[i].begin() + 1, v[i].end(), 
			[](int a, int b) { return is_clockwise(1, b, a);});
		rep(tp, 0, 1) {
			for(auto i : v[tp]) {
				while(hull.size() > 1 && is_clockwise(
					hull[hull.size() - 1], i, hull[hull.size() - 2])) hull.pop_back(); 
				hull.push_back(i);
			}
		}
		int ft = 0, bk = hull.size() - 1;
		while(true) {
			bool done = 1;
			while(is_clockwise(hull[bk], hull[ft], hull[bk - 1])) {
				done = 0, bk--;
			}
			while(is_clockwise(hull[ft], hull[ft + 1], hull[bk])) {
				done = 0, ft++;
			}
			if(done) break;
		}
		give_answer(bk - ft + 1);
		return;
	}	

};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	solve();
	return 0;
}

Compilation message (stderr)

tri.cpp:3: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    3 | #pragma loop-opt(on)
      |

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