oj.uz

답안 #727200

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
727200 2023-04-20T07:59:18 Z SanguineChameleon 육각형 영역 (APIO21_hexagon) C++17
20 / 100
 692 ms 67904 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -