Submission #727200

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
727200	2023-04-20T07:59:18 Z	SanguineChameleon	Hexagonal Territory (APIO21_hexagon)	C++17	20 / 100	692 ms	67904 KB

hexagon

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

#ifdef KAMIRULEZ
	const bool local = true;
	const int subtask = 4;
#else
	const bool local = false;
	const int subtask = -1;
#endif

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 && (!local || subtask == 1 || subtask == 2)) {
		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 && (!local || subtask == 3)) {
		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	0 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	0 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	Correct	1 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	0 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	628 ms	67772 KB	Output is correct
2	Correct	593 ms	67676 KB	Output is correct
3	Correct	627 ms	67632 KB	Output is correct
4	Correct	636 ms	67532 KB	Output is correct
5	Correct	605 ms	67652 KB	Output is correct
6	Correct	617 ms	67792 KB	Output is correct
7	Correct	600 ms	67788 KB	Output is correct
8	Correct	599 ms	67672 KB	Output is correct
9	Correct	598 ms	67776 KB	Output is correct
10	Correct	600 ms	67804 KB	Output is correct
11	Correct	594 ms	67676 KB	Output is correct
12	Correct	627 ms	67644 KB	Output is correct
13	Correct	646 ms	67904 KB	Output is correct
14	Correct	687 ms	67568 KB	Output is correct
15	Correct	605 ms	67656 KB	Output is correct
16	Correct	618 ms	67520 KB	Output is correct
17	Correct	617 ms	67660 KB	Output is correct
18	Correct	0 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	616 ms	67544 KB	Output is correct
2	Correct	630 ms	67532 KB	Output is correct
3	Correct	674 ms	67672 KB	Output is correct
4	Correct	603 ms	67564 KB	Output is correct
5	Correct	692 ms	67536 KB	Output is correct
6	Correct	606 ms	67660 KB	Output is correct
7	Correct	608 ms	67544 KB	Output is correct
8	Correct	639 ms	67676 KB	Output is correct
9	Correct	585 ms	67656 KB	Output is correct
10	Correct	587 ms	67660 KB	Output is correct
11	Correct	598 ms	67672 KB	Output is correct
12	Correct	610 ms	67692 KB	Output is correct
13	Correct	586 ms	67676 KB	Output is correct
14	Correct	584 ms	67624 KB	Output is correct
15	Correct	593 ms	67664 KB	Output is correct
16	Correct	625 ms	67660 KB	Output is correct
17	Correct	632 ms	67664 KB	Output is correct
18	Incorrect	1 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	0 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	0 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	629 ms	67672 KB	Output is correct
2	Correct	0 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	Correct	0 ms	212 KB	Output is correct
6	Correct	583 ms	67496 KB	Output is correct
7	Correct	593 ms	67656 KB	Output is correct
8	Correct	603 ms	67680 KB	Output is correct
9	Correct	606 ms	67672 KB	Output is correct
10	Correct	600 ms	67548 KB	Output is correct
11	Correct	601 ms	67536 KB	Output is correct
12	Correct	596 ms	67520 KB	Output is correct
13	Correct	585 ms	67612 KB	Output is correct
14	Correct	593 ms	67568 KB	Output is correct
15	Correct	585 ms	67648 KB	Output is correct
16	Correct	592 ms	67784 KB	Output is correct
17	Correct	597 ms	67568 KB	Output is correct
18	Correct	582 ms	67572 KB	Output is correct
19	Correct	605 ms	67568 KB	Output is correct
20	Correct	587 ms	67560 KB	Output is correct
21	Correct	597 ms	67548 KB	Output is correct
22	Incorrect	0 ms	212 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Submission #727200

Compilation message