Submission #246996

#	Time	Username	Problem	Language	Result	Execution time	Memory
246996		tonowak	Triangles (CEOI18_tri)	C++14	75 / 100	33 ms	2816 KiB

tri

#include <bits/stdc++.h> // Tomasz Nowak
#include "trilib.h"
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

int requests = 0;
bool dir_right(int a, int b, int c) {
	if(++requests > int(1e6) - 5)
		assert(false);
	return is_clockwise(a + 1, b + 1, c + 1);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n = get_n();
	debug(n);

	array<vector<int>, 2> halfplane;
	FOR(i, 2, n - 1)
		halfplane[dir_right(0, 1, i)].emplace_back(i);
	debug(halfplane);

	array<vector<int>, 2> halfhull;

	REP(iter, 2) {
		halfplane[iter].emplace_back(1);
		sort(halfplane[iter].begin(), halfplane[iter].end(), [&](int a, int b) {
			if(a == b)
				return false;		
			return dir_right(0, a, b) != iter;
		});
		halfplane[iter].emplace(halfplane[iter].begin(), 0);
		debug(halfplane[iter]);

		auto &hp = halfplane[iter], &hh = halfhull[iter];

		for(int p : hp) {
			while(size(hh) >= 2 and dir_right(hh.end()[-2], hh.back(), p) == iter)
				hh.pop_back();
			hh.emplace_back(p);
		}
		debug(iter, hh);

		if(iter)
			hh.erase(prev(hh.end()));
		else
			hh.erase(hh.begin());
		debug(iter, hh);
	}

	REP(iter, 2) {
		for(auto &hh : halfhull)
			reverse(hh.begin(), hh.end());
		debug(halfhull);

		while(true) {
			bool did = false;
			if(size(halfhull[0]) >= 2 and size(halfhull[1]) >= 1
					and dir_right(halfhull[0].end()[-2], halfhull[0].back(), halfhull[1].back()) != iter) {
				halfhull[0].pop_back();
				did = true;
			}
			if(size(halfhull[0]) >= 1 and size(halfhull[1]) >= 2
					and dir_right(halfhull[0].back(), halfhull[1].back(), halfhull[1].end()[-2]) != iter) {
				did = true;
				halfhull[1].pop_back();
			}
			if(not did)
				break;
		}
	}

	debug(halfhull);
	give_answer(size(halfhull[0]) + size(halfhull[1]));
}

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