oj.uz

Submission #466714

# Submission time Handle Problem Language Result Execution time Memory
466714 2021-08-20T13:42:03 Z rainboy Hexagonal Territory (APIO21_hexagon) C++17
21 / 100
 719 ms 28788 KB 
#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 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;
}

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(int x1, int y1, int x2, int 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_++;
}

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 = yy[ii[j]] != yy[i_] ? yy[ii[j]] - yy[i_] : (xx[ii[j]][0] + xx[ii[j]][1]) - (xx[i_][0] + xx[i_][1]);

			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 dfs(int p, int i, int d) {
	int i_ = i >> 1, s = i & 1, o, x;

	x = (long long) d * (xx[ii[i_ << 1 | 1]][s] - xx[ii[i_ << 1 | 0]][s] + 1) % MD;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			if ((i ^ j) == 1)
				x = (x + dfs(i, j, d + 1)) % MD; 
			else {
				int j_ = j >> 1, t = j & 1;

				x = (x + dfs(i, j, d)) % MD;
				x = (x - (long long) d * (min(xx[ii[j_ << 1 | 1]][t], xx[ii[i_ << 1 | 1]][s]) - max(xx[ii[j_ << 1 | 0]][t], xx[ii[i_ << 1 | 0]][s]) + 1)) % MD;
			}
		}
	}
	return x;
}

int solve() {
	int h, i, j, k, l, x, y, ans;

	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]];
	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);
			for (i = 0; i < n_ * 2; i++)
				free(ej[i]);
			break;
		}
		if (yy[i1] + 1 == 0 && xx[i1][1] <= 0 && 0 <= xx[i1][1]) {
			ans = dfs(-1, i << 1 | 1, 0);
			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 (n == 3)
		ans2 = choose3(ll[0] + 2) * 2 % MD;
	else {
		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

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 292 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 460 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 22212 KB Output is correct
2 Correct 51 ms 6012 KB Output is correct
3 Correct 70 ms 10988 KB Output is correct
4 Correct 55 ms 9552 KB Output is correct
5 Correct 82 ms 8828 KB Output is correct
6 Correct 95 ms 16720 KB Output is correct
7 Correct 45 ms 5968 KB Output is correct
8 Correct 136 ms 20728 KB Output is correct
9 Correct 139 ms 20680 KB Output is correct
10 Correct 128 ms 16976 KB Output is correct
11 Correct 75 ms 15992 KB Output is correct
12 Correct 78 ms 15236 KB Output is correct
13 Correct 78 ms 16964 KB Output is correct
14 Correct 111 ms 26356 KB Output is correct
15 Correct 125 ms 28788 KB Output is correct
16 Correct 133 ms 24516 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 86 ms 22064 KB Output is correct
4 Correct 54 ms 5956 KB Output is correct
5 Correct 69 ms 11152 KB Output is correct
6 Correct 53 ms 9644 KB Output is correct
7 Correct 83 ms 8828 KB Output is correct
8 Correct 96 ms 16704 KB Output is correct
9 Correct 44 ms 5976 KB Output is correct
10 Correct 151 ms 20696 KB Output is correct
11 Correct 131 ms 20668 KB Output is correct
12 Correct 128 ms 16916 KB Output is correct
13 Correct 76 ms 15936 KB Output is correct
14 Correct 77 ms 15172 KB Output is correct
15 Correct 75 ms 16968 KB Output is correct
16 Correct 113 ms 26364 KB Output is correct
17 Correct 116 ms 28740 KB Output is correct
18 Correct 133 ms 24548 KB Output is correct
19 Runtime error 621 ms 8216 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 460 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 292 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Runtime error 719 ms 8268 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Incorrect 1 ms 460 KB Output isn't correct
10 Halted 0 ms 0 KB -