Submission #466595

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
466595	2021-08-19T17:58:23 Z	rainboy	Hexagonal Territory (APIO21_hexagon)	C++17	47 / 100	1232 ms	270312 KB

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.0 / 3.0

#	Verdict	Memory	Grader output
1	Correct	204 KB	Output is correct
2	Correct	204 KB	Output is correct
3	Correct	204 KB	Output is correct
4	Correct	204 KB	Output is correct
5	Correct	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	1 ms	204 KB	Output is correct
3	Correct	1 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	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	303 ms	270312 KB	Output is correct
2	Correct	291 ms	264932 KB	Output is correct
3	Correct	301 ms	267940 KB	Output is correct
4	Correct	306 ms	268460 KB	Output is correct
5	Correct	313 ms	266132 KB	Output is correct
6	Correct	305 ms	268872 KB	Output is correct
7	Correct	290 ms	267960 KB	Output is correct
8	Correct	284 ms	269636 KB	Output is correct
9	Correct	298 ms	270080 KB	Output is correct
10	Correct	279 ms	269892 KB	Output is correct
11	Correct	296 ms	269620 KB	Output is correct
12	Correct	319 ms	258628 KB	Output is correct
13	Correct	290 ms	258820 KB	Output is correct
14	Correct	285 ms	258408 KB	Output is correct
15	Correct	292 ms	270104 KB	Output is correct
16	Correct	290 ms	270008 KB	Output is correct
17	Correct	294 ms	270068 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	5 ms	716 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	8 ms	1072 KB	Output is correct
12	Correct	8 ms	972 KB	Output is correct
13	Correct	9 ms	924 KB	Output is correct
14	Correct	9 ms	1096 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct

Subtask #5
15.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	0 ms	204 KB	Output is correct
4	Correct	2 ms	332 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	2 ms	332 KB	Output is correct
9	Correct	5 ms	716 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	8 ms	1068 KB	Output is correct
14	Correct	9 ms	1076 KB	Output is correct
15	Correct	8 ms	972 KB	Output is correct
16	Correct	12 ms	1092 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	14 ms	1440 KB	Output is correct
21	Correct	2 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	21 ms	1900 KB	Output is correct
24	Correct	29 ms	2924 KB	Output is correct
25	Correct	31 ms	3052 KB	Output is correct
26	Correct	15 ms	1648 KB	Output is correct
27	Correct	11 ms	1180 KB	Output is correct
28	Correct	7 ms	888 KB	Output is correct
29	Correct	33 ms	3412 KB	Output is correct
30	Correct	33 ms	3404 KB	Output is correct
31	Correct	33 ms	3396 KB	Output is correct
32	Correct	46 ms	3420 KB	Output is correct
33	Correct	21 ms	1680 KB	Output is correct
34	Correct	8 ms	972 KB	Output is correct
35	Correct	0 ms	204 KB	Output is correct
36	Correct	0 ms	204 KB	Output is correct
37	Correct	0 ms	204 KB	Output is correct

Subtask #6
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	296 ms	270236 KB	Output is correct
2	Correct	302 ms	264924 KB	Output is correct
3	Correct	294 ms	267952 KB	Output is correct
4	Correct	460 ms	268456 KB	Output is correct
5	Correct	310 ms	266084 KB	Output is correct
6	Correct	303 ms	268888 KB	Output is correct
7	Correct	311 ms	267960 KB	Output is correct
8	Correct	295 ms	269532 KB	Output is correct
9	Correct	292 ms	270084 KB	Output is correct
10	Correct	305 ms	269872 KB	Output is correct
11	Correct	279 ms	269592 KB	Output is correct
12	Correct	301 ms	258952 KB	Output is correct
13	Correct	291 ms	258668 KB	Output is correct
14	Correct	303 ms	258372 KB	Output is correct
15	Correct	305 ms	270064 KB	Output is correct
16	Correct	298 ms	270040 KB	Output is correct
17	Correct	316 ms	270132 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	2 ms	460 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	2 ms	428 KB	Output is correct
24	Correct	5 ms	844 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct
26	Correct	0 ms	204 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	14 ms	1260 KB	Output is correct
29	Correct	8 ms	1272 KB	Output is correct
30	Correct	10 ms	1100 KB	Output is correct
31	Correct	9 ms	1304 KB	Output is correct
32	Correct	1 ms	204 KB	Output is correct
33	Correct	1 ms	204 KB	Output is correct
34	Runtime error	3 ms	332 KB	Execution killed with signal 11
35	Halted	0 ms	0 KB	-

Subtask #7
0 / 18.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	Runtime error	1232 ms	272 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	310 ms	270276 KB	Output is correct
2	Correct	0 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
6	Correct	298 ms	264928 KB	Output is correct
7	Correct	315 ms	267872 KB	Output is correct
8	Correct	294 ms	268516 KB	Output is correct
9	Correct	323 ms	266084 KB	Output is correct
10	Correct	299 ms	268916 KB	Output is correct
11	Correct	304 ms	268036 KB	Output is correct
12	Correct	334 ms	269560 KB	Output is correct
13	Correct	299 ms	270084 KB	Output is correct
14	Correct	312 ms	269864 KB	Output is correct
15	Correct	299 ms	269632 KB	Output is correct
16	Correct	301 ms	258632 KB	Output is correct
17	Correct	297 ms	258724 KB	Output is correct
18	Correct	304 ms	258320 KB	Output is correct
19	Correct	305 ms	270068 KB	Output is correct
20	Correct	318 ms	270020 KB	Output is correct
21	Correct	302 ms	270012 KB	Output is correct
22	Correct	0 ms	204 KB	Output is correct
23	Correct	2 ms	332 KB	Output is correct
24	Correct	1 ms	204 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	2 ms	436 KB	Output is correct
28	Correct	6 ms	924 KB	Output is correct
29	Correct	1 ms	204 KB	Output is correct
30	Correct	1 ms	204 KB	Output is correct
31	Correct	1 ms	204 KB	Output is correct
32	Correct	8 ms	1196 KB	Output is correct
33	Correct	12 ms	1228 KB	Output is correct
34	Correct	8 ms	1108 KB	Output is correct
35	Correct	9 ms	1328 KB	Output is correct
36	Correct	1 ms	204 KB	Output is correct
37	Correct	1 ms	204 KB	Output is correct
38	Correct	0 ms	204 KB	Output is correct
39	Correct	14 ms	2064 KB	Output is correct
40	Correct	2 ms	460 KB	Output is correct
41	Correct	1 ms	332 KB	Output is correct
42	Correct	19 ms	2656 KB	Output is correct
43	Correct	32 ms	4064 KB	Output is correct
44	Correct	34 ms	4400 KB	Output is correct
45	Correct	15 ms	2308 KB	Output is correct
46	Correct	12 ms	1740 KB	Output is correct
47	Correct	10 ms	1220 KB	Output is correct
48	Correct	35 ms	4684 KB	Output is correct
49	Correct	34 ms	4676 KB	Output is correct
50	Correct	33 ms	4672 KB	Output is correct
51	Correct	34 ms	4392 KB	Output is correct
52	Correct	16 ms	2184 KB	Output is correct
53	Correct	10 ms	1180 KB	Output is correct
54	Runtime error	3 ms	332 KB	Execution killed with signal 11
55	Halted	0 ms	0 KB	-

Submission #466595

Compilation message