oj.uz

Submission #727233

# Submission time Handle Problem Language Result Execution time Memory
727233 2023-04-20T09:16:39 Z SanguineChameleon Hexagonal Territory (APIO21_hexagon) C++17
47 / 100
 695 ms 67812 KB 
#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef KAMIRULEZ
	const bool local = true;
	const int subtask = 5;
#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};

struct point {
	long long x, y;

	point() {};

	point(long long _x, long long _y): x(_x), y(_y) {};

	point operator*(long long d) {
		return point(x * d, y * d);
	}

	point operator+(point p2) {
		return point(x + p2.x, y + p2.y);
	}

	long long operator^(point p2) {
		return x * p2.y - y * p2.x;
	}
};

point dv[7] = {point(0, 0), point(0, 1), point(1, 1), point(1, 0), point(0, -1), point(-1, -1), point(-1, 0)};

ostream& operator<<(ostream &out, point p) {
	out << "(" << p.x << "," << p.y << ")";
	return out;
}

struct line {
	int type, dir, len;
	point p1, p2;

	line() {};

	line(int _type, int _dir, point _p1, point _p2): type(_type), dir(_dir), p1(_p1), p2(_p2) {
		len = p2.x - p1.x + 1;
	};

	long long calc() {
		long long res = 0;
		long long Ly = p1.y;
		long long Ry = p1.y + (dir == 1 ? 0 : len - 1);
		if (type == 1) {
			Ly = 1 - Ly;
			Ry = 1 - Ry;
		}
		return (Ly + Ry) % mod * len % mod * one_half % mod;
	}
};

ostream& operator<<(ostream &out, line L) {
	if (L.type == 1) {
		out << "bottom line, ";
	}
	else {
		out << "top line, ";
	}
	if (L.dir == 1) {
		out << "straight, ";
	}
	else {
		out << "diagonal, ";
	}
	out << "from" << " " << L.p1 << " to " << L.p2;
	return out;
}

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;
	}
	long long area = 0;
	point cur = point(0, 0);
	vector<point> poly(N);
	for (int i = 0; i < N; i++) {
		poly[i] = cur;
		cur = cur + (dv[D[i]] * L[i]);
	}
	for (int i = 0; i < N; i++) {
		area += poly[i] ^ poly[(i + 1) % N];
	}
	if (area < 0) {
		reverse(D.begin(), D.end());
		for (int i = 0; i < N; i++) {
			if (D[i] <= 3) {
				D[i] += 3;
			}
			else {
				D[i] -= 3;
			}
		}
		reverse(L.begin(), L.end());
		cur = point(0, 0);
		for (int i = 0; i < N; i++) {
			poly[i] = cur;
			cur = cur + (dv[D[i]] * L[i]);
		}
	}
	vector<line> lines;
	for (int i = 0; i < N; i++) {
		point prv = poly[(i + (N - 1)) % N];
		point cur = poly[i];
		point nxt1 = poly[(i + 1) % N];
		point nxt2 = poly[(i + 2) % N];
		if (cur.x < nxt1.x) {
			point p1 = cur;
			point p2 = nxt1;
			int dir = (cur.y == nxt1.y ? 1 : 2);
			if (prv.x < cur.x) {
				if (dir == 1) {
					p1 = p1 + point(1, 0);
				}
				else {
					p1 = p1 + point(1, 1);
				}
			}
			if (prv.x == cur.x && prv.y < cur.y) {
				if (dir == 1) {
					p1 = p1 + point(1, 0);
				}
				else {
					p1 = p1 + point(1, 1);
				}
			}
			if (nxt1.x == nxt2.x && nxt1.y > nxt2.y) {
				if (dir == 1) {
					p2 = p2 + point(-1, 0);
				}
				else {
					p2 = p2 + point(-1, -1);
				}
			}
			if (p1.x <= p2.x) {
				lines.emplace_back(1, dir, p1, p2);
			}
		}
		if (cur.x > nxt1.x) {
			point p1 = nxt1;
			point p2 = cur;
			int dir = (cur.y == nxt1.y ? 1 : 2);
			if (prv.x > cur.x) {
				if (dir == 1) {
					p2 = p2 + point(-1, 0);
				}
				else {
					p2 = p2 + point(-1, -1);
				}
			}
			if (prv.x == cur.x && prv.y > cur.y) {
				if (dir == 1) {
					p2 = p2 + point(-1, 0);
				}
				else {
					p2 = p2 + point(-1, -1);
				}
			}
			if (nxt1.x == nxt2.x && nxt1.y < nxt2.y) {
				if (dir == 1) {
					p1 = p1 + point(1, 0);
				}
				else {
					p1 = p1 + point(1, 1);
				}
			}
			if (p1.x <= p2.x) {
				lines.emplace_back(2, dir, p1, p2);
			}
		}
	}
	if (B == 0 && (!local || subtask == 4 || subtask == 5)) {
		long long res = 0;
		for (auto L: lines) {
			res += L.calc();
			res %= mod;
		}
		if (res < 0) {
			res += mod;
		}
		res = res * A % mod;
		return res;
	}
	return 0;
}

Compilation message

hexagon.cpp: In member function 'long long int line::calc()':
hexagon.cpp:57:13: warning: unused variable 'res' [-Wunused-variable]
   57 |   long long res = 0;
      |             ^~~

Subtask #1
3.0 / 3.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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 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 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
6 Correct 1 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 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 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 614 ms 67556 KB Output is correct
2 Correct 657 ms 67660 KB Output is correct
3 Correct 604 ms 67688 KB Output is correct
4 Correct 637 ms 67564 KB Output is correct
5 Correct 620 ms 67564 KB Output is correct
6 Correct 611 ms 67680 KB Output is correct
7 Correct 641 ms 67784 KB Output is correct
8 Correct 617 ms 67512 KB Output is correct
9 Correct 618 ms 67524 KB Output is correct
10 Correct 620 ms 67564 KB Output is correct
11 Correct 652 ms 67660 KB Output is correct
12 Correct 639 ms 67812 KB Output is correct
13 Correct 595 ms 67616 KB Output is correct
14 Correct 635 ms 67672 KB Output is correct
15 Correct 622 ms 67808 KB Output is correct
16 Correct 623 ms 67704 KB Output is correct
17 Correct 668 ms 67656 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 1048 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 1044 KB Output is correct
7 Correct 8 ms 2892 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 308 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 11 ms 4936 KB Output is correct
12 Correct 10 ms 3508 KB Output is correct
13 Correct 9 ms 3356 KB Output is correct
14 Correct 12 ms 5060 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct

Subtask #5
15.0 / 15.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 2 ms 1048 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 3 ms 1044 KB Output is correct
9 Correct 9 ms 2968 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 12 ms 4936 KB Output is correct
14 Correct 10 ms 3532 KB Output is correct
15 Correct 11 ms 3404 KB Output is correct
16 Correct 11 ms 5064 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 19 ms 5960 KB Output is correct
21 Correct 3 ms 1144 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 25 ms 10600 KB Output is correct
24 Correct 43 ms 13016 KB Output is correct
25 Correct 49 ms 13500 KB Output is correct
26 Correct 18 ms 6952 KB Output is correct
27 Correct 14 ms 5952 KB Output is correct
28 Correct 9 ms 3656 KB Output is correct
29 Correct 48 ms 20260 KB Output is correct
30 Correct 43 ms 14140 KB Output is correct
31 Correct 45 ms 14116 KB Output is correct
32 Correct 45 ms 20036 KB Output is correct
33 Correct 21 ms 6908 KB Output is correct
34 Correct 11 ms 3660 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 67560 KB Output is correct
2 Correct 623 ms 67652 KB Output is correct
3 Correct 635 ms 67636 KB Output is correct
4 Correct 602 ms 67656 KB Output is correct
5 Correct 604 ms 67788 KB Output is correct
6 Correct 610 ms 67736 KB Output is correct
7 Correct 650 ms 67784 KB Output is correct
8 Correct 627 ms 67784 KB Output is correct
9 Correct 642 ms 67560 KB Output is correct
10 Correct 627 ms 67660 KB Output is correct
11 Correct 605 ms 67620 KB Output is correct
12 Correct 642 ms 67648 KB Output is correct
13 Correct 608 ms 67792 KB Output is correct
14 Correct 615 ms 67556 KB Output is correct
15 Correct 651 ms 67564 KB Output is correct
16 Correct 624 ms 67668 KB Output is correct
17 Correct 616 ms 67532 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 2 ms 1048 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 3 ms 1044 KB Output is correct
24 Correct 8 ms 2968 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 16 ms 4936 KB Output is correct
29 Correct 11 ms 3504 KB Output is correct
30 Correct 13 ms 3352 KB Output is correct
31 Correct 15 ms 5052 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Incorrect 0 ms 212 KB Output isn't correct
35 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 1 ms 212 KB Output is correct
4 Correct 0 ms 240 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 605 ms 67564 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 603 ms 67804 KB Output is correct
7 Correct 613 ms 67684 KB Output is correct
8 Correct 633 ms 67624 KB Output is correct
9 Correct 638 ms 67660 KB Output is correct
10 Correct 626 ms 67688 KB Output is correct
11 Correct 650 ms 67560 KB Output is correct
12 Correct 643 ms 67568 KB Output is correct
13 Correct 695 ms 67680 KB Output is correct
14 Correct 637 ms 67676 KB Output is correct
15 Correct 629 ms 67612 KB Output is correct
16 Correct 606 ms 67644 KB Output is correct
17 Correct 621 ms 67788 KB Output is correct
18 Correct 622 ms 67532 KB Output is correct
19 Correct 609 ms 67564 KB Output is correct
20 Correct 634 ms 67780 KB Output is correct
21 Correct 679 ms 67536 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 2 ms 1068 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 2 ms 1044 KB Output is correct
28 Correct 7 ms 2972 KB Output is correct
29 Correct 1 ms 464 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 11 ms 5032 KB Output is correct
33 Correct 12 ms 3512 KB Output is correct
34 Correct 10 ms 3404 KB Output is correct
35 Correct 11 ms 5124 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 17 ms 5912 KB Output is correct
40 Correct 3 ms 1144 KB Output is correct
41 Correct 1 ms 724 KB Output is correct
42 Correct 24 ms 10692 KB Output is correct
43 Correct 39 ms 13116 KB Output is correct
44 Correct 41 ms 13500 KB Output is correct
45 Correct 19 ms 6984 KB Output is correct
46 Correct 14 ms 5960 KB Output is correct
47 Correct 10 ms 3660 KB Output is correct
48 Correct 46 ms 20280 KB Output is correct
49 Correct 41 ms 14128 KB Output is correct
50 Correct 40 ms 14116 KB Output is correct
51 Correct 46 ms 20016 KB Output is correct
52 Correct 20 ms 6920 KB Output is correct
53 Correct 10 ms 3660 KB Output is correct
54 Incorrect 0 ms 212 KB Output isn't correct
55 Halted 0 ms 0 KB -