Submission #466595

#	Time	Username	Problem	Language	Result	Execution time	Memory
466595		rainboy	Hexagonal Territory (APIO21_hexagon)	C++17	47 / 100	1232 ms	270312 KiB

hexagon

#include "hexagon.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

const int MD = 1000000007, V2 = 500000004, V6 = 166666668, INF = 0x3f3f3f3f, X = 2000;

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

int dx[] = { 1, 1, 0, -1, -1, 0 };
int dy[] = { 0, 1, 1, 0, -1, -1 };

int choose2(int n) {
	return (long long) n * (n - 1) % MD * V2 % MD;
}

int choose3(int n) {
	return (long long) n * (n - 1) % MD * (n - 2) % MD * V6 % MD;
}

char grid[X][X + 1]; int dd[X][X], qu[X * X], head, cnt;

void dfs(int x, int y, char c) {
	int h;

	if (x < 0 || x >= X || y < 0 || y >= X || grid[x][y])
		return;
	grid[x][y] = c;
	for (h = 0; h < 6; h++)
		dfs(x + dx[h], y + dy[h], c);
}

long long cross(int x1, int y1, int x2, int y2) {
	return (long long) x1 * y2 - (long long) x2 * y1;
}

int draw_territory(int n, int a, int b, vi hh, vi ll) {
	int h, i, l, x, y, x_, y_, ans1, ans2;
	long long area2, boundary, internal;

	if (n == 3)
		ans1 = choose2(ll[0] + 2), ans2 = choose3(ll[0] + 2) * 2 % MD;
	else if (b == 0) {
		x = 0, y = 0, area2 = 0, boundary = 0;
		for (i = 0; i < n; i++) {
			h = hh[i] - 1;
			area2 += cross(x, y, x + dx[h] * ll[i], y + dy[h] * ll[i]);
			boundary += ll[i];
			x += dx[h] * ll[i], y += dy[h] * ll[i];
		}
		if (area2 < 0)
			area2 = -area2;
		internal = (area2 - boundary) / 2 + 1;
		ans1 = (boundary + internal) % MD, ans2 = 0;
	} else {
		x = 1, y = 1;
		for (i = 0; i < n; i++) {
			h = hh[i] - 1;
			for (l = 0; l < ll[i]; l++)
				x = max(x + dx[h], 1), y = max(y + dy[h], 1);
		}
		x_ = x, y_ = y;
		for (i = 0; i < n; i++) {
			h = hh[i] - 1;
			for (l = 0; l < ll[i]; l++)
				grid[x += dx[h]][y += dy[h]] = 'X';
		}
		dfs(0, 0, ' ');
		for (x = 0; x < X; x++)
			for (y = 0; y < X; y++)
				dfs(x, y, 'O');
		ans1 = 0;
		for (x = 0; x < X; x++)
			for (y = 0; y < X; y++) {
				dd[x][y] = INF;
				if (grid[x][y] != ' ')
					ans1++;
			}
		dd[x_][y_] = 0, qu[head + cnt++] = x_ * X + y_;
		ans2 = 0;
		while (cnt) {
			int xy, d;

			xy = qu[cnt--, head++], x = xy / X, y = xy % X, d = dd[x][y] + 1;
			ans2 = (ans2 + dd[x][y]) % MD;
			for (h = 0; h < 6; h++) {
				int x_ = x + dx[h], y_ = y + dy[h];

				if (x_ >= 0 && x_ < X && y_ >= 0 && y_ < X && grid[x_][y_] != ' ' && dd[x_][y_] > d)
					dd[x_][y_] = d, qu[head + cnt++] = x_ * X + y_;
			}
		}
	}
	return ((long long) ans1 * a + (long long) ans2 * b) % MD;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16