Submission #828582

#	Time	Username	Problem	Language	Result	Execution time	Memory
828582		MadokaMagicaFan	Triangles (CEOI18_tri)	C++14	100 / 100	256 ms	2216 KiB

tri

#include "bits/stdc++.h"
#include "trilib.h"
using namespace std;
#define sz(v) ((int)v.size())
#define pb push_back
#define chk is_clockwise

#define indx(j)   ((j + sz(ch)) % sz(ch))

void rem(vector<int> &c, int i) {
	for (int j = i+1; j < sz(c); ++j)
		c[j-1] = c[j];
	c.pop_back();
}

void ins(vector<int> &c, int i, int x) {
	c.pb(0);
	for (int j = sz(c) -1; j >i; --j)
		c[j] = c[j-1];
	c[i] = x;
}

int main() {
	int n = get_n();
	vector<int> ch = {1, 2, 3};
	if (!chk(1,2,3))
		swap(ch[1], ch[2]);

	for (int j = 4; j <= n; ++j) {
		int l = 1, r = sz(ch);
		assert(sz(ch) >=3);
		while (l < r) {
			int m = (l+r)/2;
			if (chk(ch[0], j, ch[m]))
				r = m;
			else
				l = m+1;
		}

		if (l > 1 && l != sz(ch)) {
			if (chk(ch[0], ch[l-1], j) && chk(ch[l-1], ch[l], j) && chk(ch[l], ch[0], j))
				continue;
		}

		ins(ch, l, j);
		while (chk(ch[indx(l-2)], ch[l], ch[indx(l-1)])) {
			int u = indx(l-1);
			rem(ch, u);
			if (u < l) --l;
		}

		while (chk(ch[indx(l+1)], ch[l], ch[indx(l+2)])) {
			int u = indx(l+1);
			rem(ch, u);
			if (u < l) --l;
		}
	}

	give_answer(sz(ch));
}

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