oj.uz

Submission #466589

# Submission time Handle Problem Language Result Execution time Memory
466589 2021-08-19T17:38:44 Z rainboy Hexagonal Territory (APIO21_hexagon) C++17
20 / 100
 1225 ms 270232 KB 
#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]; int dd[X][X], qu[X * X], head, cnt;

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

	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);
}

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_, y_;

		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;
}

Compilation message

hexagon.cpp: In function 'void dfs(int, int, char)':
hexagon.cpp:26:9: warning: unused variable 'x_' [-Wunused-variable]
   26 |  int h, x_, y_;
      |         ^~
hexagon.cpp:26:13: warning: unused variable 'y_' [-Wunused-variable]
   26 |  int h, x_, y_;
      |             ^~

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 1 ms 204 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 1 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 1 ms 204 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 270196 KB Output is correct
2 Correct 278 ms 265024 KB Output is correct
3 Correct 298 ms 267924 KB Output is correct
4 Correct 297 ms 268452 KB Output is correct
5 Correct 273 ms 266072 KB Output is correct
6 Correct 295 ms 268800 KB Output is correct
7 Correct 292 ms 268100 KB Output is correct
8 Correct 277 ms 269764 KB Output is correct
9 Correct 307 ms 270032 KB Output is correct
10 Correct 284 ms 269940 KB Output is correct
11 Correct 285 ms 269620 KB Output is correct
12 Correct 321 ms 258628 KB Output is correct
13 Correct 290 ms 258696 KB Output is correct
14 Correct 295 ms 258396 KB Output is correct
15 Correct 289 ms 270148 KB Output is correct
16 Correct 287 ms 270020 KB Output is correct
17 Correct 296 ms 270032 KB Output is correct
18 Correct 1 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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 332 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 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Runtime error 3 ms 332 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 270208 KB Output is correct
2 Correct 294 ms 265032 KB Output is correct
3 Correct 301 ms 267908 KB Output is correct
4 Correct 290 ms 268508 KB Output is correct
5 Correct 292 ms 266056 KB Output is correct
6 Correct 318 ms 268868 KB Output is correct
7 Correct 291 ms 268156 KB Output is correct
8 Correct 293 ms 269608 KB Output is correct
9 Correct 274 ms 270104 KB Output is correct
10 Correct 286 ms 269868 KB Output is correct
11 Correct 287 ms 269616 KB Output is correct
12 Correct 288 ms 258680 KB Output is correct
13 Correct 301 ms 258720 KB Output is correct
14 Correct 283 ms 258400 KB Output is correct
15 Correct 298 ms 270216 KB Output is correct
16 Correct 300 ms 270020 KB Output is correct
17 Correct 275 ms 270008 KB Output is correct
18 Runtime error 3 ms 336 KB Execution killed with signal 11
19 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 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 Runtime error 1225 ms 264 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 292 ms 270232 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 1 ms 204 KB Output is correct
6 Correct 295 ms 265008 KB Output is correct
7 Correct 277 ms 267944 KB Output is correct
8 Correct 308 ms 268436 KB Output is correct
9 Correct 284 ms 266080 KB Output is correct
10 Correct 297 ms 268912 KB Output is correct
11 Correct 286 ms 267972 KB Output is correct
12 Correct 295 ms 269612 KB Output is correct
13 Correct 281 ms 270084 KB Output is correct
14 Correct 278 ms 269868 KB Output is correct
15 Correct 302 ms 269724 KB Output is correct
16 Correct 290 ms 258616 KB Output is correct
17 Correct 281 ms 258740 KB Output is correct
18 Correct 279 ms 258420 KB Output is correct
19 Correct 287 ms 270064 KB Output is correct
20 Correct 306 ms 270160 KB Output is correct
21 Correct 296 ms 270068 KB Output is correct
22 Runtime error 3 ms 332 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -