Submission #1208658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208658		k1r1t0	Hexagonal Territory (APIO21_hexagon)	C++20	47 / 100	803 ms	897888 KiB

hexagon

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MOD = (int)(1e9+7);
const int INV6 = (MOD + 1) / 6;
const int T = 2100;

vector<array<int, 2>> d = {{0, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, 0}, {-1, 1}};
int a[T + T][T + T];

void dfs(int i, int j) {
	if (a[i][j] != -1)
		return;
	a[i][j] = 0;
	for (auto [dx, dy] : d)
		if (0 <= i + dx && 0 <= j + dy && i + dx < T + T && j + dy < T + T)
			dfs(i + dx, j + dy);
}

int draw_territory(int N, int A, int B, vector<int> D, vector<int> L) {
	if (N == 3) {
		ll t = L[0];
		return ((t + 1) * A % MOD + t * (t + 1) / 2 % MOD * (A + B) % MOD + t * (t + 1) % MOD * (2 * t + 1) % MOD * INV6 % MOD * B % MOD) % MOD;
	}
	ll sum = 0;
	for (auto x : L)
		sum += x;
	if (sum <= 2000) {
		ll x = 0, y = 0;
		for (int i = 0; i < T + T; i++)
		for (int j = 0; j < T + T; j++)
			a[i][j] = -1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < L[i]; j++) {
				x += d[D[i] - 1][0];
				y += d[D[i] - 1][1];
				a[T + x][T + y] = 1;
			}
		}
		dfs(0, 0);
		for (int i = 0; i < T + T; i++)
		for (int j = 0; j < T + T; j++)
			if (a[i][j] == 1)
				a[i][j] = -1;
		a[T][T] = 0;
		queue<array<int, 2>> qq;
		qq.push({T, T});
		while (!qq.empty()) {
			auto [i, j] = qq.front(); qq.pop();
			for (auto [dx, dy] : d)
				if (0 <= i + dx && 0 <= j + dy && i + dx < T + T && j + dy < T + T && a[i + dx][j + dy] == -1) {
					a[i + dx][j + dy] = a[i][j] + 1;
					qq.push({i + dx, j + dy});
				}
		}
		int ans = A;
		for (int i = 0; i < T + T; i++)
		for (int j = 0; j < T + T; j++)
			if (a[i][j] > 0)
				(ans += (A + 1ll * B * a[i][j]) % MOD) %= MOD;
		return ans;
	}
	ll s = 0, b = 0, x = 0, y = 0;
	for (int i = 0; i < N; i++) {
		b += L[i];
		ll nx = x + d[D[i] - 1][0] * L[i];
		ll ny = y + d[D[i] - 1][1] * L[i];
		s += x * ny - y * nx;
		x = nx, y = ny;
	}
	s = abs(s) / 2;
	ll p = s - b / 2 + 1;
	return A * ((p + b) % MOD) % MOD;
}

• 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