Submission #466748

#	Time	Username	Problem	Language	Result	Execution time	Memory
466748		rainboy	Hexagonal Territory (APIO21_hexagon)	C++17	36 / 100	41 ms	4940 KiB

hexagon

#include "hexagon.h"
#include <stdlib.h>
#include <vector>
 
using namespace std;
 
typedef vector<int> vi;
 
const int N = 200000, MD = 1000000007, V2 = 500000004, V6 = 166666668;
 
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
 
unsigned int X = 12345;
 
int rand_() {
	return (X *= 3) >> 1;
}
 
int dx[] = { 1, 1, 0, -1, -1, 0 };
int dy[] = { 0, 1, 1, 0, -1, -1 };
 
int sum1(int n) {
	return (long long) n * (n + 1) % MD * V2 % MD;
}

int sum2(int n) {
	return (long long) n * (n + 1) % MD * (n * 2 + 1) % MD * V6 % MD;
}

long long cross(int x1, int y1, int x2, int y2) {
	return (long long) x1 * y2 - (long long) x2 * y1;
}
 
int hh[N], ll[N], ii[N], xx[N][2], yy[N], n, n_;
 
void add(long long x1, long long y1, long long x2, long long y2) {
	if (y1 < y2)
		xx[n_][0] = x1, xx[n_][1] = x2, yy[n_] = y1, n_++;
	else if (y1 > y2)
		xx[n_][0] = x2, xx[n_][1] = x1, yy[n_] = y2, n_++;
}
 
int compare(int i, int j) {
	int c = yy[i] != yy[j] ? yy[i] - yy[j] : (xx[i][0] + xx[i][1]) - (xx[j][0] + xx[j][1]);
 
	return c == 0 ? 0 : (c < 0 ? -1 : 1);
}
 
void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
 
		while (j < k) {
			int c = compare(ii[j], i_);
 
			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}
 
int *ej[N], eo[N];
 
void append(int i, int j) {
	int o = eo[i]++;
 
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}
 
int area(int xi1, int xi2, int xj1, int xj2, int z, int l) {
	int d = ((xj2 - xj1) - (xi2 - xi1)) / l, x = xi2 - xi1 + 1;
 
	/* sum_{1}^{l-1} (x + d h) (z + h)
	 * = sum_{1}^{l-1} d h^2 + (x + z d) h + x z
	 * = d sum2(l - 1) + (x + z d) sum1(l - 1) + x z
	 */
	return (sum2(l - 1) * d + (long long) (x + z * d) * sum1(l - 1) + (long long) x * z) % MD;
}
 
int dfs(int p, int i, int d, int l) {
	int i_, s, xi1, xi2, o, x;
 
	i_ = i >> 1, s = i & 1, xi1 = xx[ii[i_ << 1 | 0]][s], xi2 = xx[ii[i_ << 1 | 1]][s];
	x = (long long) d * (xi2 - xi1 + 1) % MD;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];
 
		if (j != p) {
			int j_ = j >> 1, t = j & 1, xj1 = xx[ii[j_ << 1 | 0]][t], xj2 = xx[ii[j_ << 1 | 1]][t];
 
			if ((i ^ j) == 1)
				x = (x + dfs(i, j, d + l, l) + area(xi1, xi2, xj1, xj2, d, l)) % MD; 
			else {
				x = (x + dfs(i, j, d, l)) % MD;
				x = (x - (long long) d * (min(xi2, xj2) - max(xi1, xj1) + 1)) % MD;
			}
		}
	}
	return x;
}
 
int solve() {
	int l_, h, i, j, k, l, x, y, ans;
 
	l_ = ll[0];
	for (i = 0; i < n; i++)
		if (ll[i] != ll[0]) {
			l_ = 1;
			break;
		}
	if (l_ == 1) {
		n_ = 0, x = 0, y = 0;
		for (i = 0; i < n; i++)
			for (l = 0; l < ll[i]; l++)
				add(x, y, x + dx[hh[i]], y + dy[hh[i]]), x += dx[hh[i]], y += dy[hh[i]];
	} else {
		n_ = 0, x = 0, y = 0;
		for (i = 0; i < n; i++)
			add(x, y, x + dx[hh[i]] * l_, y + dy[hh[i]] * l_), x += dx[hh[i]] * l_, y += dy[hh[i]] * l_;
	}
	for (i = 0; i < n_; i++)
		ii[i] = i;
	sort(ii, 0, n_);
	n_ /= 2;
	for (i = 0; i < n_ * 2; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	for (i = 0; i < n_; i++)
		append(i << 1 | 0, i << 1 | 1), append(i << 1 | 1, i << 1 | 0);
	for (h = -1, i = 0; i < n_; h = i, i = j) {
		int y = yy[ii[i << 1 | 0]];
 
		j = i + 1;
		while (j < n_ && yy[ii[j << 1 | 0]] == y)
			j++;
		if (h != -1) {
			k = h, l = i;
			while (k < i && l < j)
				if (xx[ii[k << 1 | 1]][1] < xx[ii[l << 1 | 1]][0]) {
					if (xx[ii[l << 1 | 0]][0] <= xx[ii[k << 1 | 1]][1])
						append(k << 1 | 1, l << 1 | 0), append(l << 1 | 0, k << 1 | 1);
					k++;
				} else {
					if (xx[ii[k << 1 | 0]][1] <= xx[ii[l << 1 | 1]][0])
						append(k << 1 | 1, l << 1 | 0), append(l << 1 | 0, k << 1 | 1);
					l++;
				}
		}
	}
	ans = 0;
	for (i = 0; i < n_; i++) {
		int i0 = ii[i << 1 | 0], i1 = ii[i << 1 | 1];
 
		if (yy[i0] == 0 && xx[i0][0] <= 0 && 0 <= xx[i1][0]) {
			ans = dfs(-1, i << 1 | 0, 0, l_);
			for (i = 0; i < n_ * 2; i++)
				free(ej[i]);
			break;
		}
		if (yy[i1] + l_ == 0 && xx[i0][1] <= 0 && 0 <= xx[i1][1]) {
			ans = dfs(-1, i << 1 | 1, 0, l_);
			for (i = 0; i < n_ * 2; i++)
				free(ej[i]);
			break;
		}
	}
	return ans;
}
 
int draw_territory(int n_, int a, int b, vi hh_, vi ll_) {
	int h, i, x, y, ans1, ans2;
	long long area2, boundary, internal;
 
	n = n_;
	for (i = 0; i < n; i++)
		hh[i] = hh_[i] - 1, ll[i] = ll_[i];
	x = 0, y = 0, area2 = 0, boundary = 0;
	for (i = 0; i < n; i++) {
		h = hh[i];
		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;
	if (b > 0) {
		ans2 = 0;
		for (h = 0; h < 3; h++) {
			ans2 = (ans2 + solve()) % MD;
			for (i = 0; i < n; i++)
				hh[i] = (hh[i] + 1) % 6;
		}
		if (ans2 < 0)
			ans2 += MD;
		ans2 = (long long) ans2 * V2 % MD;
	}
	return ((long long) ans1 * a + (long long) ans2 * b) % MD;
}

Compilation message (stderr)

hexagon.cpp: In function 'void append(int, int)':
hexagon.cpp:77:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   77 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

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