Submission #544765

#	Time	Username	Problem	Language	Result	Execution time	Memory
544765		rainboy	Meandian (CEOI06_meandian)	C++11	100 / 100	6 ms	208 KiB

meandian

#include "libmean.h"

#define N	100

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int main() {
	static int aa[N + 1];
	int n, i, i1, i2, i3, i4, j, j1, j2, j3, j4, a2, x;

	n = Init();
	if (n == 4) {
		aa[0] = aa[1] = aa[2] = aa[3] = -1;
		Solution(aa);
		return 0;
	}
	i1 = 1, i2 = 2, i3 = 3, i4 = 4, x = Meandian(i1, i2, i3, i4);
	for (i = 5; i <= n; i++) {
		int x1 = Meandian(i, i2, i3, i4), x2 = Meandian(i1, i, i3, i4), x3 = Meandian(i1, i2, i, i4), x4 = Meandian(i1, i2, i3, i), x_ = min(min(x1, x2), min(x3, x4));

		if (x > x_) {
			if (x1 == x_)
				i1 = i;
			else if (x2 == x_)
				i2 = i;
			else if (x3 == x_)
				i3 = i;
			else if (x4 == x_)
				i4 = i;
			x = x_;
		}
	}
	a2 = -1;
	for (i = 1; i <= n; i++)
		if (i1 != i && i2 != i && i3 != i && i4 != i) {
			int x1 = Meandian(i, i2, i3, i4), x2 = Meandian(i1, i, i3, i4), x3 = Meandian(i1, i2, i, i4), x4 = Meandian(i1, i2, i3, i), tmp;

			if (x1 < x2)
				tmp = i1, i1 = i2, i2 = tmp, tmp = x1, x1 = x2, x2 = tmp;
			if (x1 < x3)
				tmp = i1, i1 = i3, i3 = tmp, tmp = x1, x1 = x3, x3 = tmp;
			if (x1 < x4)
				tmp = i1, i1 = i4, i4 = tmp, tmp = x1, x1 = x4, x4 = tmp;
			if (x2 < x3)
				tmp = i2, i2 = i3, i3 = tmp, tmp = x2, x2 = x3, x3 = tmp;
			if (x2 < x4)
				tmp = i2, i2 = i4, i4 = tmp, tmp = x2, x2 = x4, x4 = tmp;
			if (x3 < x4)
				tmp = i3, i3 = i4, i4 = tmp, tmp = x3, x3 = x4, x4 = tmp;
			a2 = x3 + x4 - x1;
			break;
		}
	j1 = 1, j2 = 2, j3 = 3, j4 = 4, x = Meandian(j1, j2, j3, j4);
	for (j = 5; j <= n; j++) {
		int x_;

		if (x < (x_ = Meandian(j, j2, j3, j4)))
			j1 = j, x = x_;
		else if (x < (x_ = Meandian(j1, j, j3, j4)))
			j2 = j, x = x_;
	}
	for (j = 1; j <= n; j++)
		if (j1 != j && j2 != j && j3 != j && j4 != j) {
			int x1 = Meandian(j, j2, j3, j4), x2 = Meandian(j1, j, j3, j4), x3 = Meandian(j1, j2, j, j4), x4 = Meandian(j1, j2, j3, j), tmp;

			if (x1 > x2)
				tmp = j1, j1 = j2, j2 = tmp, tmp = x1, x1 = x2, x2 = tmp;
			if (x1 > x3)
				tmp = j1, j1 = j3, j3 = tmp, tmp = x1, x1 = x3, x3 = tmp;
			if (x1 > x4)
				tmp = j1, j1 = j4, j4 = tmp, tmp = x1, x1 = x4, x4 = tmp;
			if (x2 > x3)
				tmp = j2, j2 = j3, j3 = tmp, tmp = x2, x2 = x3, x3 = tmp;
			if (x2 > x4)
				tmp = j2, j2 = j4, j4 = tmp, tmp = x2, x2 = x4, x4 = tmp;
			if (x3 > x4)
				tmp = j3, j3 = j4, j4 = tmp, tmp = x3, x3 = x4, x4 = tmp;
			break;
		}
	for (i = 1; i <= n; i++)
		aa[i] = i != i1 && i != i2 && i != j1 && i != j2 ? Meandian(i1, i2, i, j1) * 2 - a2 : -1;
	Solution(aa + 1);
	return 0;
}

• Subtask 1: 100 / 100