Submission #727199

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
727199	2023-04-20T07:55:17 Z	SanguineChameleon	Hexagonal Territory (APIO21_hexagon)	C++17	20 / 100	710 ms	67816 KB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;

const long long mod = 1e9 + 7;
const long long one_half = (mod + 1) / 2;
const long long one_third = (mod + 1) / 3;
const int dx[7] = {0, 0, 1, 1, 0, -1, -1};
const int dy[7] = {0, 1, 1, 0, -1, -1, 0};

int draw_territory(int N, int A, int B, vector<int> D, vector<int> L) {
	if (N == 3) {
		int len = L[0] + 1;
		long long A_sum = 1LL * len * (len + 1) % mod * one_half % mod;
		long long B_sum = 1LL * len * (len - 1) % mod * one_half % mod + (len - 1) * len % mod * (len * 2 - 1) % mod * one_half % mod * one_third % mod;
		return (A_sum * A + B_sum * B) % mod;
	}
	long long L_sum = 0;
	for (int i = 0; i < N; i++) {
		L_sum += L[i];
	}
	if (L_sum <= 2000) {
		vector<vector<bool>> border(4069, vector<bool>(4069, false));
		vector<vector<int>> dist(4069, vector<int>(4069, -1));
		int cx = 0;
		int cy = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < L[i]; j++) {
				cx += dx[D[i]];
				cy += dy[D[i]];
				border[cx + 2023][cy + 2023] = true;
			}
		}
		deque<pair<int, int>> q = {{0, 0}};
		dist[0][0] = -2;
		while (!q.empty()) {
			cx = q.front().first;
			cy = q.front().second;
			q.pop_front();
			for (int d = 1; d <= 6; d++) {
				int nx = cx + dx[d];
				int ny = cy + dy[d];
				if (0 <= nx && nx < 4069 && 0 <= ny && ny < 4069 && !border[nx][ny] && dist[nx][ny] == -1) {
					dist[nx][ny] = -2;
					q.push_back({nx, ny});
				}
			}
		}
		q.push_back({2023, 2023});
		dist[2023][2023] = 0;
		long long res = 0;
		while (!q.empty()) {
			cx = q.front().first;
			cy = q.front().second;
			res += 1LL * B * dist[cx][cy] + A;
			res %= mod;
			q.pop_front();
			for (int d = 1; d <= 6; d++) {
				int nx = cx + dx[d];
				int ny = cy + dy[d];
				if (0 <= nx && nx < 4069 && 0 <= ny && ny < 4069 && dist[nx][ny] == -1) {
					dist[nx][ny] = dist[cx][cy] + 1;
					q.push_back({nx, ny});
				}
			}
		}
		return res;
	}
	return 0;
}

Subtask #1
3.0 / 3.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	617 ms	67540 KB	Output is correct
2	Correct	612 ms	67564 KB	Output is correct
3	Correct	600 ms	67668 KB	Output is correct
4	Correct	604 ms	67680 KB	Output is correct
5	Correct	619 ms	67540 KB	Output is correct
6	Correct	646 ms	67564 KB	Output is correct
7	Correct	597 ms	67568 KB	Output is correct
8	Correct	635 ms	67688 KB	Output is correct
9	Correct	692 ms	67684 KB	Output is correct
10	Correct	664 ms	67556 KB	Output is correct
11	Correct	640 ms	67816 KB	Output is correct
12	Correct	638 ms	67680 KB	Output is correct
13	Correct	638 ms	67680 KB	Output is correct
14	Correct	628 ms	67536 KB	Output is correct
15	Correct	635 ms	67680 KB	Output is correct
16	Correct	609 ms	67556 KB	Output is correct
17	Correct	625 ms	67680 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 15.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Incorrect	212 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #6
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	634 ms	67560 KB	Output is correct
2	Correct	608 ms	67660 KB	Output is correct
3	Correct	632 ms	67784 KB	Output is correct
4	Correct	618 ms	67780 KB	Output is correct
5	Correct	636 ms	67788 KB	Output is correct
6	Correct	607 ms	67552 KB	Output is correct
7	Correct	628 ms	67588 KB	Output is correct
8	Correct	650 ms	67676 KB	Output is correct
9	Correct	657 ms	67664 KB	Output is correct
10	Correct	639 ms	67660 KB	Output is correct
11	Correct	601 ms	67448 KB	Output is correct
12	Correct	604 ms	67564 KB	Output is correct
13	Correct	628 ms	67792 KB	Output is correct
14	Correct	627 ms	67660 KB	Output is correct
15	Correct	648 ms	67668 KB	Output is correct
16	Correct	644 ms	67564 KB	Output is correct
17	Correct	672 ms	67516 KB	Output is correct
18	Incorrect	0 ms	212 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #7
0 / 18.0

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

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	678 ms	67560 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	710 ms	67564 KB	Output is correct
7	Correct	617 ms	67808 KB	Output is correct
8	Correct	629 ms	67648 KB	Output is correct
9	Correct	642 ms	67568 KB	Output is correct
10	Correct	627 ms	67576 KB	Output is correct
11	Correct	674 ms	67672 KB	Output is correct
12	Correct	657 ms	67696 KB	Output is correct
13	Correct	624 ms	67788 KB	Output is correct
14	Correct	617 ms	67664 KB	Output is correct
15	Correct	623 ms	67784 KB	Output is correct
16	Correct	615 ms	67656 KB	Output is correct
17	Correct	623 ms	67572 KB	Output is correct
18	Correct	606 ms	67532 KB	Output is correct
19	Correct	626 ms	67780 KB	Output is correct
20	Correct	669 ms	67656 KB	Output is correct
21	Correct	646 ms	67672 KB	Output is correct
22	Incorrect	1 ms	212 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Submission #727199

Compilation message