Submission #1166307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166307		sleepntsheep	Triangles (CEOI18_tri)	C11	0 / 100	1 ms	832 KiB

tri

#include <stdio.h>
#include "trilib.h"
#include <string.h>
#include <stdlib.h>

int sta[55555], top, n, low[55555], q, w, a[55555], b[55555], c, d, ch_high[55555], ch_low[55555], cha, chb
		, sta2[55555], top2;

int cmp_high(const void *ii, const void *jj) {
	return ! is_clockwise(q, *(int*)ii, *(int*)jj);
}

int cmp_low(const void *ii, const void *jj) {
	return ! is_clockwise(q, *(int*)ii, *(int*)jj);
}



int main() {
	n = get_n();

	q = 1;
	w = 2;

	for (int i = 3; i <= n; ++i) {
		if (is_clockwise(q, w, i)) {
			low[i] = 1;
			a[c++] = i;
		} else {
			low[i] = 0;
			b[d++] = i;
		}
	}

	qsort(b, d, sizeof *b, cmp_high);
	qsort(a, c, sizeof *a, cmp_low);

	sta[top = 1] = w;
	sta[top = 2] = q;

	for (int i = 0; i < d; ++i) {
		int j = b[i];
		while (top > 2 && is_clockwise(sta[top - 1], sta[top], j))
			--top;
		sta[++top] = j;
	}

	cha = top;
	memcpy(ch_high, sta, sizeof sta);

	sta[top = 1] = q;
	sta[top = 2] = w;
	for (int i = 0; i < c; ++i) {
		int j = a[i];
		while (top > 2 && is_clockwise(sta[top - 1], sta[top], j))
			--top;
		sta[++top] = j;
	}

	chb = top;
	memcpy(ch_low, sta, sizeof sta);

	/* stitch around q */

	int sta = 0, stb = 0;
	while (cha - sta > 1 && chb - stb > 1) {
		int f = 0;
		if (cha - sta > 1 && chb - stb > 2 && is_clockwise(ch_high[cha ], ch_low[stb + 1], ch_low[stb + 2])) {
			++stb;
			++f;
		}
		if (cha - sta > 1 && chb - stb > 2 && is_clockwise(ch_low[chb - 1], ch_low[chb - 0], ch_high[sta + 1])) {
			--chb;
			++f;
		}

		if (chb - stb > 1 && cha - sta > 2 && is_clockwise(ch_low[chb ], ch_high[sta + 1], ch_high[sta + 2])) {
			++sta;
			++f;
		}
		if (chb - stb > 1 && cha - sta > 2 && is_clockwise(ch_high[cha - 1], ch_high[cha - 0], ch_low[stb + 1])) {
			--cha;
			++f;
		}

		if (! f)
			break;
	}

	give_answer(cha + chb - sta - stb);
	return 0;
}

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