#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;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
795 ms |
1048580 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
171 ms |
230760 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
819 ms |
1048580 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
827 ms |
1048580 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |