oj.uz

Submission #727358

# Submission time Handle Problem Language Result Execution time Memory
727358 2023-04-20T12:54:19 Z SanguineChameleon Hexagonal Territory (APIO21_hexagon) C++17
47 / 100
 668 ms 106412 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 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 1 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 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 1 ms 300 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 304 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 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 621 ms 67628 KB Output is correct
2 Correct 607 ms 67676 KB Output is correct
3 Correct 637 ms 67564 KB Output is correct
4 Correct 636 ms 67552 KB Output is correct
5 Correct 652 ms 67676 KB Output is correct
6 Correct 629 ms 67532 KB Output is correct
7 Correct 607 ms 67572 KB Output is correct
8 Correct 608 ms 67580 KB Output is correct
9 Correct 631 ms 67692 KB Output is correct
10 Correct 626 ms 67556 KB Output is correct
11 Correct 602 ms 67528 KB Output is correct
12 Correct 623 ms 67568 KB Output is correct
13 Correct 620 ms 67688 KB Output is correct
14 Correct 606 ms 67516 KB Output is correct
15 Correct 657 ms 67676 KB Output is correct
16 Correct 640 ms 67680 KB Output is correct
17 Correct 632 ms 67664 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 296 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 7 ms 3152 KB Output is correct
3 Correct 2 ms 944 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 5 ms 1948 KB Output is correct
6 Correct 10 ms 3620 KB Output is correct
7 Correct 32 ms 9692 KB Output is correct
8 Correct 2 ms 720 KB Output is correct
9 Correct 1 ms 692 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 48 ms 24720 KB Output is correct
12 Correct 32 ms 14336 KB Output is correct
13 Correct 32 ms 13564 KB Output is correct
14 Correct 48 ms 17672 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 468 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 304 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 7 ms 3160 KB Output is correct
5 Correct 2 ms 976 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 5 ms 1948 KB Output is correct
8 Correct 10 ms 3544 KB Output is correct
9 Correct 32 ms 9764 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 46 ms 24724 KB Output is correct
14 Correct 31 ms 14420 KB Output is correct
15 Correct 23 ms 13652 KB Output is correct
16 Correct 49 ms 17660 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 1 ms 428 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 69 ms 27440 KB Output is correct
21 Correct 7 ms 3416 KB Output is correct
22 Correct 3 ms 1664 KB Output is correct
23 Correct 90 ms 35636 KB Output is correct
24 Correct 165 ms 61520 KB Output is correct
25 Correct 175 ms 62692 KB Output is correct
26 Correct 97 ms 33632 KB Output is correct
27 Correct 61 ms 25604 KB Output is correct
28 Correct 45 ms 16276 KB Output is correct
29 Correct 227 ms 106412 KB Output is correct
30 Correct 115 ms 57048 KB Output is correct
31 Correct 118 ms 57060 KB Output is correct
32 Correct 250 ms 85924 KB Output is correct
33 Correct 65 ms 28080 KB Output is correct
34 Correct 30 ms 12452 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 593 ms 67560 KB Output is correct
2 Correct 633 ms 67772 KB Output is correct
3 Correct 602 ms 67660 KB Output is correct
4 Correct 647 ms 67680 KB Output is correct
5 Correct 668 ms 67652 KB Output is correct
6 Correct 608 ms 67780 KB Output is correct
7 Correct 609 ms 67648 KB Output is correct
8 Correct 606 ms 67488 KB Output is correct
9 Correct 603 ms 67644 KB Output is correct
10 Correct 608 ms 67656 KB Output is correct
11 Correct 621 ms 67664 KB Output is correct
12 Correct 648 ms 67576 KB Output is correct
13 Correct 643 ms 67576 KB Output is correct
14 Correct 613 ms 67684 KB Output is correct
15 Correct 613 ms 67788 KB Output is correct
16 Correct 644 ms 67532 KB Output is correct
17 Correct 630 ms 67916 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 7 ms 3256 KB Output is correct
20 Correct 2 ms 976 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 4 ms 1948 KB Output is correct
23 Correct 7 ms 3616 KB Output is correct
24 Correct 25 ms 9756 KB Output is correct
25 Correct 2 ms 756 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 53 ms 24764 KB Output is correct
29 Correct 32 ms 14364 KB Output is correct
30 Correct 24 ms 13584 KB Output is correct
31 Correct 47 ms 17652 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Correct 1 ms 424 KB Output is correct
34 Incorrect 1 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 0 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 611 ms 67564 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 212 KB Output is correct
6 Correct 622 ms 67564 KB Output is correct
7 Correct 615 ms 67792 KB Output is correct
8 Correct 619 ms 67560 KB Output is correct
9 Correct 647 ms 67544 KB Output is correct
10 Correct 630 ms 67680 KB Output is correct
11 Correct 664 ms 67564 KB Output is correct
12 Correct 619 ms 67812 KB Output is correct
13 Correct 628 ms 67660 KB Output is correct
14 Correct 607 ms 67660 KB Output is correct
15 Correct 626 ms 67788 KB Output is correct
16 Correct 626 ms 67820 KB Output is correct
17 Correct 598 ms 67664 KB Output is correct
18 Correct 605 ms 67692 KB Output is correct
19 Correct 641 ms 67620 KB Output is correct
20 Correct 602 ms 67640 KB Output is correct
21 Correct 613 ms 67648 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 7 ms 3288 KB Output is correct
24 Correct 2 ms 976 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 5 ms 1948 KB Output is correct
27 Correct 8 ms 3640 KB Output is correct
28 Correct 27 ms 9696 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 468 KB Output is correct
32 Correct 48 ms 24768 KB Output is correct
33 Correct 30 ms 14412 KB Output is correct
34 Correct 24 ms 13612 KB Output is correct
35 Correct 47 ms 17656 KB Output is correct
36 Correct 1 ms 596 KB Output is correct
37 Correct 1 ms 432 KB Output is correct
38 Correct 1 ms 304 KB Output is correct
39 Correct 71 ms 27424 KB Output is correct
40 Correct 8 ms 3416 KB Output is correct
41 Correct 5 ms 1704 KB Output is correct
42 Correct 92 ms 35520 KB Output is correct
43 Correct 165 ms 61536 KB Output is correct
44 Correct 173 ms 62640 KB Output is correct
45 Correct 88 ms 33576 KB Output is correct
46 Correct 62 ms 25460 KB Output is correct
47 Correct 42 ms 16320 KB Output is correct
48 Correct 252 ms 106412 KB Output is correct
49 Correct 111 ms 57096 KB Output is correct
50 Correct 115 ms 57192 KB Output is correct
51 Correct 224 ms 86092 KB Output is correct
52 Correct 65 ms 28020 KB Output is correct
53 Correct 30 ms 12500 KB Output is correct
54 Incorrect 1 ms 300 KB Output isn't correct
55 Halted 0 ms 0 KB -