oj.uz

Submission #466588

# Submission time Handle Problem Language Result Execution time Memory
466588 2021-08-19T17:27:49 Z rainboy Hexagonal Territory (APIO21_hexagon) C++17
9 / 100
 827 ms 1048580 KB 
#include "hexagon.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

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

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 + 1 + X][X + 1 + X + 1]; int dd[X + 1 + X][X + 1 + X], qu[(X + 1 + X) * (X + 1 + X)], head, cnt;

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

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

int draw_territory(int n, int a, int b, vi hh, vi ll) {
	int ans1, ans2;

	if (n == 3)
		ans1 = choose2(ll[0] + 2), ans2 = choose3(ll[0] + 2) * 2 % MD;
	else {
		int i, h, l, x, y;

		x = X, y = X;
		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 * 2; x++)
			for (y = 0; y <= X * 2; y++)
				dfs(x, y, 'O');
		ans1 = 0;
		for (x = 0; x <= X * 2; x++)
			for (y = 0; y <= X * 2; y++) {
				dd[x][y] = INF;
				if (grid[x][y] != ' ')
					ans1++;
			}
		ans2 = 0;
		dd[X][X] = 0, qu[head + cnt++] = X * (X * 2 + 1) + X;
		while (cnt) {
			int xy, d;

			xy = qu[cnt--, head++], x = xy / (X * 2 + 1), y = xy % (X * 2 + 1), 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 * 2 && y_ >= 0 && y_ <= X * 2 && grid[x_][y_] != ' ' && dd[x_][y_] > d)
					dd[x_][y_] = d, qu[head + cnt++] = x_ * (X * 2 + 1) + y_;
			}
		}
	}
	return ((long long) ans1 * a + (long long) ans2 * b) % MD;
}

Subtask #1
3.0 / 3.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 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

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 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 1 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 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 288 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 795 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 171 ms 230760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Runtime error 181 ms 230632 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 819 ms 1048580 KB Execution killed with signal 9
2 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 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Runtime error 42 ms 25100 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 827 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -