oj.uz

Submission #727229

# Submission time Handle Problem Language Result Execution time Memory
727229 2023-04-20T09:12:15 Z SanguineChameleon Hexagonal Territory (APIO21_hexagon) C++17
32 / 100
 2000 ms 67804 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};

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;
		for (int i = 0; i < len; i++) {
			long long y = p1.y + (dir == 1 ? 0 : i);
			if (type == 1) {
				res -= y - 1;
				res %= mod;
			}
			else {
				res += y;
				res %= mod;
			}
		}
		if (res < 0) {
			res += mod;
		}
		return res;
	}
};

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)) {
		long long res = 0;
		for (auto L: lines) {
			res += L.calc();
			res %= mod;
		}
		if (res < 0) {
			res += mod;
		}
		res = res * A % mod;
		return res;
	}
/*	if (L_sum <= 200000 && (!local || subtask == 4)) {
		int cx = 0;
		int cy = 0;
		set<pair<int, int>> S;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < L[i]; j++) {
				cx += dx[D[i]];
				cy += dy[D[i]];
				S.insert({cx, cy});
			}
		}
		long long res = 0;
		for (auto p: S) {
			cx = p.first;
			cy = p.second;
			if (S.find(make_pair(cx, cy + 1)) == S.end()) {
				cout << cx << " " << cy << " " << "top" << '\n';
				res += cy;
				res %= mod;
			}
			if (S.find(make_pair(cx, cy - 1)) == S.end()) {
				cout << cx << " " << cy << " " << "bottom" << '\n';
				res -= cy - 1;
				res %= mod;
			}
			cout << res << '\n';
		}
		if (res < mod) {
			res += mod;
		}
		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 1 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 1 ms 296 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 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 1 ms 212 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 67568 KB Output is correct
2 Correct 623 ms 67668 KB Output is correct
3 Correct 647 ms 67696 KB Output is correct
4 Correct 639 ms 67520 KB Output is correct
5 Correct 624 ms 67544 KB Output is correct
6 Correct 639 ms 67684 KB Output is correct
7 Correct 632 ms 67556 KB Output is correct
8 Correct 604 ms 67556 KB Output is correct
9 Correct 663 ms 67564 KB Output is correct
10 Correct 655 ms 67776 KB Output is correct
11 Correct 669 ms 67680 KB Output is correct
12 Correct 601 ms 67688 KB Output is correct
13 Correct 621 ms 67520 KB Output is correct
14 Correct 648 ms 67572 KB Output is correct
15 Correct 627 ms 67656 KB Output is correct
16 Correct 601 ms 67568 KB Output is correct
17 Correct 625 ms 67676 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
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 3 ms 1024 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 764 KB Output is correct
6 Correct 3 ms 1044 KB Output is correct
7 Correct 9 ms 3108 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 12 ms 5192 KB Output is correct
12 Correct 12 ms 3708 KB Output is correct
13 Correct 10 ms 3532 KB Output is correct
14 Correct 14 ms 5292 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct

Subtask #5
0 / 15.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 1 ms 212 KB Output is correct
4 Correct 3 ms 1048 KB Output is correct
5 Correct 1 ms 436 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 4 ms 1144 KB Output is correct
9 Correct 10 ms 3020 KB Output is correct
10 Correct 2 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 5192 KB Output is correct
14 Correct 11 ms 3756 KB Output is correct
15 Correct 10 ms 3536 KB Output is correct
16 Correct 13 ms 5292 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1481 ms 284 KB Output is correct
20 Execution timed out 2041 ms 6472 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 67660 KB Output is correct
2 Correct 622 ms 67552 KB Output is correct
3 Correct 624 ms 67624 KB Output is correct
4 Correct 603 ms 67556 KB Output is correct
5 Correct 647 ms 67784 KB Output is correct
6 Correct 648 ms 67592 KB Output is correct
7 Correct 653 ms 67660 KB Output is correct
8 Correct 626 ms 67484 KB Output is correct
9 Correct 622 ms 67516 KB Output is correct
10 Correct 625 ms 67660 KB Output is correct
11 Correct 633 ms 67656 KB Output is correct
12 Correct 613 ms 67564 KB Output is correct
13 Correct 621 ms 67788 KB Output is correct
14 Correct 620 ms 67784 KB Output is correct
15 Correct 662 ms 67660 KB Output is correct
16 Correct 635 ms 67564 KB Output is correct
17 Correct 666 ms 67688 KB Output is correct
18 Correct 1 ms 284 KB Output is correct
19 Correct 3 ms 1104 KB Output is correct
20 Correct 1 ms 436 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 764 KB Output is correct
23 Correct 3 ms 1044 KB Output is correct
24 Correct 9 ms 3088 KB Output is correct
25 Correct 1 ms 428 KB Output is correct
26 Correct 1 ms 304 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 16 ms 5224 KB Output is correct
29 Correct 12 ms 3660 KB Output is correct
30 Correct 11 ms 3632 KB Output is correct
31 Correct 12 ms 5320 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 296 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 1 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 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 619 ms 67804 KB Output is correct
2 Correct 1 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 1 ms 300 KB Output is correct
6 Correct 650 ms 67692 KB Output is correct
7 Correct 627 ms 67516 KB Output is correct
8 Correct 611 ms 67784 KB Output is correct
9 Correct 619 ms 67568 KB Output is correct
10 Correct 595 ms 67560 KB Output is correct
11 Correct 670 ms 67516 KB Output is correct
12 Correct 607 ms 67540 KB Output is correct
13 Correct 654 ms 67572 KB Output is correct
14 Correct 615 ms 67556 KB Output is correct
15 Correct 626 ms 67628 KB Output is correct
16 Correct 650 ms 67532 KB Output is correct
17 Correct 677 ms 67672 KB Output is correct
18 Correct 650 ms 67800 KB Output is correct
19 Correct 634 ms 67572 KB Output is correct
20 Correct 645 ms 67572 KB Output is correct
21 Correct 607 ms 67532 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 3 ms 1048 KB Output is correct
24 Correct 2 ms 432 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 2 ms 760 KB Output is correct
27 Correct 3 ms 1140 KB Output is correct
28 Correct 8 ms 3120 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 12 ms 5192 KB Output is correct
33 Correct 11 ms 3660 KB Output is correct
34 Correct 11 ms 3604 KB Output is correct
35 Correct 12 ms 5288 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1475 ms 280 KB Output is correct
39 Execution timed out 2045 ms 6472 KB Time limit exceeded
40 Halted 0 ms 0 KB -