oj.uz

Submission #727770

# Submission time Handle Problem Language Result Execution time Memory
727770 2023-04-21T09:46:27 Z SanguineChameleon Hexagonal Territory (APIO21_hexagon) C++17
47 / 100
 659 ms 106436 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, id;
	point p1, p2;

	line() {};

	line(int _type, int _dir, point _p1, point _p2, int _id): type(_type), dir(_dir), p1(_p1), p2(_p2), id(_id) {
		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;
	}

	long long eval_x(long long x) {
		if (dir == 1) {
			return p1.y;
		}
		else {
			return p1.y + (x - p1.x);
		}
	}

	void shorten(long long left_x, long long right_x) {
		long long v1 = eval_x(left_x);
		long long v2 = eval_x(right_x);
		p1 = point(left_x, v1);
		p2 = point(right_x, v2);
	}
};

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

bool operator<(line L1, line L2) {
	int max_x = max(L1.p1.x, L2.p1.x);
	int v1 = L1.eval_x(max_x);
	int v2 = L2.eval_x(max_x);
	if (v1 != v2) {
		return v1 < v2;
	}
	else {
		return L1.type < L2.type;
	}
};

struct comp {
	line bottom, top;
	int left_x, right_x, len;

	comp(line _bottom, line _top, int _left_x, int _right_x): bottom(_bottom), top(_top), left_x(_left_x), right_x(_right_x) {
		bottom.shorten(left_x, right_x);
		top.shorten(left_x, right_x);
		len = right_x - left_x + 1;
	}

	long long calc() {
		long long Ly = top.p1.y - bottom.p1.y + 1;
		long long Ry = top.p2.y - bottom.p2.y + 1;
		return (Ly + Ry) % mod * len % mod * one_half % mod;
	}
};

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;
	vector<int> prv_x;
	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, lines.size());
				prv_x.push_back(p1.x);
			}
		}
		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, lines.size());
				prv_x.push_back(p1.x);
			}
		}
	}
	vector<pair<int, pair<int, line>>> events;
	for (auto L: lines) {
		events.push_back({L.p1.x - 1, {2, L}});
		events.push_back({L.p1.x, {0, L}});
		events.push_back({L.p2.x, {1, L}});
	}
	sort(events.begin(), events.end());
	set<line, less<>> S;
	vector<comp> comps;
	for (auto e: events) {
		int cur_x = e.first;
		int type = e.second.first;
		line L = e.second.second;
		auto it = (type == 0 ? S.insert(L).first : S.lower_bound(L));
		if (type == 1) {
			if (it->type == 1 && next(it) != S.end()) {
				auto bottom = it;
				auto top = next(it);
				if (prv_x[bottom->id] <= cur_x && prv_x[top->id] <= cur_x) {
					assert(prv_x[bottom->id] == prv_x[top->id]);
					comps.emplace_back(*bottom, *top, prv_x[bottom->id], cur_x);
					prv_x[bottom->id] = cur_x + 1;
					prv_x[top->id] = cur_x + 1;
				}
			}
			if (it->type == 2 && it != S.begin()) {
				auto bottom = prev(it);
				auto top = it;
				if (prv_x[bottom->id] <= cur_x && prv_x[top->id] <= cur_x) {
					assert(prv_x[bottom->id] == prv_x[top->id]);
					comps.emplace_back(*bottom, *top, prv_x[bottom->id], cur_x);
					prv_x[bottom->id] = cur_x + 1;
					prv_x[top->id] = cur_x + 1;
				}
			}
			S.erase(it);
		}
		if (type == 2) {
			if (it != S.end() && it != S.begin()) {
				auto bottom = prev(it);
				auto top = it;
				if (bottom->type == 1 && top->type == 2) {
					if (prv_x[bottom->id] <= cur_x && prv_x[top->id] <= cur_x) {
						assert(prv_x[bottom->id] == prv_x[top->id]);
						comps.emplace_back(*bottom, *top, prv_x[bottom->id], cur_x);
						prv_x[bottom->id] = cur_x + 1;
						prv_x[top->id] = cur_x + 1;
					}
				}
			}
		}
	}
	if (B == 0 && (!local || subtask == 4 || subtask == 5)) {
		long long res = 0;
		for (auto C: comps) {
			res += C.calc();
			res %= mod;
		}
		if (res < 0) {
			res += mod;
		}
		res = res * A % mod;
		return res;
	}
	return 0;
}

Compilation message

hexagon.cpp: In constructor 'line::line(int, int, point, point, int)':
hexagon.cpp:48:12: warning: 'line::p2' will be initialized after [-Wreorder]
   48 |  point p1, p2;
      |            ^~
hexagon.cpp:47:22: warning:   'int line::id' [-Wreorder]
   47 |  int type, dir, len, id;
      |                      ^~
hexagon.cpp:52:2: warning:   when initialized here [-Wreorder]
   52 |  line(int _type, int _dir, point _p1, point _p2, int _id): type(_type), dir(_dir), p1(_p1), p2(_p2), id(_id) {
      |  ^~~~
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 1 ms 212 KB Output is correct
2 Correct 1 ms 292 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 300 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 598 ms 67572 KB Output is correct
2 Correct 602 ms 67672 KB Output is correct
3 Correct 613 ms 67660 KB Output is correct
4 Correct 613 ms 67660 KB Output is correct
5 Correct 603 ms 67660 KB Output is correct
6 Correct 614 ms 67568 KB Output is correct
7 Correct 608 ms 67680 KB Output is correct
8 Correct 614 ms 67572 KB Output is correct
9 Correct 609 ms 67664 KB Output is correct
10 Correct 612 ms 67556 KB Output is correct
11 Correct 600 ms 67784 KB Output is correct
12 Correct 588 ms 67628 KB Output is correct
13 Correct 604 ms 67676 KB Output is correct
14 Correct 611 ms 67572 KB Output is correct
15 Correct 628 ms 67568 KB Output is correct
16 Correct 622 ms 67520 KB Output is correct
17 Correct 616 ms 67528 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 300 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 212 KB Output is correct
2 Correct 6 ms 3260 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 5 ms 1948 KB Output is correct
6 Correct 8 ms 3608 KB Output is correct
7 Correct 24 ms 9680 KB Output is correct
8 Correct 2 ms 756 KB Output is correct
9 Correct 1 ms 684 KB Output is correct
10 Correct 1 ms 552 KB Output is correct
11 Correct 45 ms 24740 KB Output is correct
12 Correct 30 ms 14348 KB Output is correct
13 Correct 22 ms 13648 KB Output is correct
14 Correct 46 ms 17684 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 424 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct

Subtask #5
15.0 / 15.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 296 KB Output is correct
4 Correct 6 ms 3220 KB Output is correct
5 Correct 2 ms 976 KB Output is correct
6 Correct 1 ms 560 KB Output is correct
7 Correct 4 ms 1924 KB Output is correct
8 Correct 7 ms 3544 KB Output is correct
9 Correct 26 ms 9672 KB Output is correct
10 Correct 2 ms 756 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 47 ms 24820 KB Output is correct
14 Correct 29 ms 14360 KB Output is correct
15 Correct 23 ms 13648 KB Output is correct
16 Correct 47 ms 17712 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 432 KB Output is correct
19 Correct 0 ms 300 KB Output is correct
20 Correct 63 ms 27528 KB Output is correct
21 Correct 7 ms 3416 KB Output is correct
22 Correct 3 ms 1692 KB Output is correct
23 Correct 82 ms 35484 KB Output is correct
24 Correct 155 ms 61452 KB Output is correct
25 Correct 152 ms 62688 KB Output is correct
26 Correct 82 ms 33632 KB Output is correct
27 Correct 61 ms 25396 KB Output is correct
28 Correct 41 ms 16256 KB Output is correct
29 Correct 236 ms 106432 KB Output is correct
30 Correct 112 ms 57076 KB Output is correct
31 Correct 113 ms 57096 KB Output is correct
32 Correct 208 ms 85864 KB Output is correct
33 Correct 64 ms 28080 KB Output is correct
34 Correct 30 ms 12500 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 300 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 67684 KB Output is correct
2 Correct 607 ms 67568 KB Output is correct
3 Correct 625 ms 67572 KB Output is correct
4 Correct 612 ms 67792 KB Output is correct
5 Correct 616 ms 67668 KB Output is correct
6 Correct 620 ms 67448 KB Output is correct
7 Correct 627 ms 67672 KB Output is correct
8 Correct 613 ms 67620 KB Output is correct
9 Correct 607 ms 67548 KB Output is correct
10 Correct 621 ms 67564 KB Output is correct
11 Correct 606 ms 67676 KB Output is correct
12 Correct 611 ms 67676 KB Output is correct
13 Correct 605 ms 67672 KB Output is correct
14 Correct 602 ms 67584 KB Output is correct
15 Correct 622 ms 67700 KB Output is correct
16 Correct 605 ms 67552 KB Output is correct
17 Correct 597 ms 67480 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 6 ms 3288 KB Output is correct
20 Correct 2 ms 976 KB Output is correct
21 Correct 1 ms 560 KB Output is correct
22 Correct 4 ms 1968 KB Output is correct
23 Correct 8 ms 3632 KB Output is correct
24 Correct 23 ms 9684 KB Output is correct
25 Correct 1 ms 756 KB Output is correct
26 Correct 1 ms 724 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 48 ms 24760 KB Output is correct
29 Correct 29 ms 14380 KB Output is correct
30 Correct 23 ms 13648 KB Output is correct
31 Correct 48 ms 17644 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Incorrect 0 ms 300 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #7
0 / 18.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 304 KB Output is correct
4 Correct 1 ms 296 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 624 ms 67804 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 597 ms 67660 KB Output is correct
7 Correct 659 ms 67568 KB Output is correct
8 Correct 610 ms 67660 KB Output is correct
9 Correct 613 ms 67664 KB Output is correct
10 Correct 603 ms 67560 KB Output is correct
11 Correct 599 ms 67568 KB Output is correct
12 Correct 609 ms 67652 KB Output is correct
13 Correct 609 ms 67556 KB Output is correct
14 Correct 601 ms 67448 KB Output is correct
15 Correct 603 ms 67680 KB Output is correct
16 Correct 614 ms 67568 KB Output is correct
17 Correct 604 ms 67656 KB Output is correct
18 Correct 604 ms 67576 KB Output is correct
19 Correct 605 ms 67676 KB Output is correct
20 Correct 609 ms 67692 KB Output is correct
21 Correct 629 ms 67776 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 7 ms 3256 KB Output is correct
24 Correct 2 ms 976 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 4 ms 1948 KB Output is correct
27 Correct 8 ms 3544 KB Output is correct
28 Correct 24 ms 9736 KB Output is correct
29 Correct 2 ms 756 KB Output is correct
30 Correct 1 ms 724 KB Output is correct
31 Correct 1 ms 552 KB Output is correct
32 Correct 49 ms 24760 KB Output is correct
33 Correct 29 ms 14408 KB Output is correct
34 Correct 23 ms 13616 KB Output is correct
35 Correct 53 ms 17632 KB Output is correct
36 Correct 1 ms 596 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 1 ms 300 KB Output is correct
39 Correct 65 ms 27412 KB Output is correct
40 Correct 7 ms 3396 KB Output is correct
41 Correct 3 ms 1692 KB Output is correct
42 Correct 83 ms 35496 KB Output is correct
43 Correct 159 ms 61484 KB Output is correct
44 Correct 150 ms 62660 KB Output is correct
45 Correct 86 ms 33632 KB Output is correct
46 Correct 62 ms 25516 KB Output is correct
47 Correct 41 ms 16304 KB Output is correct
48 Correct 245 ms 106436 KB Output is correct
49 Correct 117 ms 57100 KB Output is correct
50 Correct 130 ms 57064 KB Output is correct
51 Correct 219 ms 85828 KB Output is correct
52 Correct 67 ms 28080 KB Output is correct
53 Correct 39 ms 12396 KB Output is correct
54 Incorrect 1 ms 300 KB Output isn't correct
55 Halted 0 ms 0 KB -