oj.uz

Submission #727794

# Submission time Handle Problem Language Result Execution time Memory
727794 2023-04-21T10:39:20 Z SanguineChameleon Hexagonal Territory (APIO21_hexagon) C++17
47 / 100
 689 ms 67804 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;
	}
};

ostream& operator<<(ostream &out, comp C) {
	out << "(" << C.bottom << "," << C.top << "," << "(" << C.left_x << "," << C.right_x << "))";
	return out;
}

vector<comp> comps;
vector<vector<int>> adj;

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, int>>> events;
	for (int i = 0; i < (int)lines.size(); i++) {
		events.push_back(make_pair(lines[i].p1.x - 1, make_pair(2, i)));
		events.push_back(make_pair(lines[i].p1.x, make_pair(0, i)));
		events.push_back(make_pair(lines[i].p2.x, make_pair(1, i)));
	}
	sort(events.begin(), events.end());
	set<line, less<>> S;
	for (auto e: events) {
		int cur_x = e.first;
		int type = e.second.first;
		line L = lines[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;
					}
				}
			}
		}
	}
	adj.resize(comps.size());
	events.clear();
	for (int i = 0; i < (int)comps.size(); i++) {
		events.push_back(make_pair(comps[i].right_x + 1, make_pair(comps[i].bottom.p2.y, i)));
		events.push_back(make_pair(comps[i].left_x, make_pair(comps[i].bottom.p1.y, -i - 1)));
	}
	sort(events.begin(), events.end());
	int lid = -1;
	int rid = -1;
	int edge_cnt = 0;
	for (auto e: events) {
		if (e.second.second >= 0) {
			lid = e.second.second;
		}
		else {
			rid = -e.second.second - 1;
		}
		if (lid >= 0 && rid >= 0 && comps[lid].right_x + 1 == comps[rid].left_x && max(comps[lid].bottom.p2.y, comps[rid].bottom.p1.y) <= min(comps[lid].top.p2.y, comps[rid].top.p1.y)) {
			adj[lid].push_back(rid);
			adj[rid].push_back(lid);
			edge_cnt++;
		}
	}
	assert(edge_cnt + 1 == (int)comps.size());
	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 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 0 ms 212 KB Output is correct
6 Correct 0 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 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 615 ms 67692 KB Output is correct
2 Correct 608 ms 67524 KB Output is correct
3 Correct 593 ms 67656 KB Output is correct
4 Correct 622 ms 67572 KB Output is correct
5 Correct 617 ms 67668 KB Output is correct
6 Correct 609 ms 67512 KB Output is correct
7 Correct 616 ms 67532 KB Output is correct
8 Correct 615 ms 67568 KB Output is correct
9 Correct 604 ms 67780 KB Output is correct
10 Correct 612 ms 67516 KB Output is correct
11 Correct 600 ms 67636 KB Output is correct
12 Correct 608 ms 67568 KB Output is correct
13 Correct 604 ms 67668 KB Output is correct
14 Correct 598 ms 67660 KB Output is correct
15 Correct 611 ms 67560 KB Output is correct
16 Correct 606 ms 67568 KB Output is correct
17 Correct 604 ms 67788 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 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 6 ms 2172 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 4 ms 1316 KB Output is correct
6 Correct 7 ms 2188 KB Output is correct
7 Correct 25 ms 5980 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 40 ms 16308 KB Output is correct
12 Correct 25 ms 8504 KB Output is correct
13 Correct 21 ms 8244 KB Output is correct
14 Correct 42 ms 11480 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 7 ms 2172 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 5 ms 1316 KB Output is correct
8 Correct 8 ms 2200 KB Output is correct
9 Correct 24 ms 5980 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 40 ms 16328 KB Output is correct
14 Correct 24 ms 8504 KB Output is correct
15 Correct 21 ms 8220 KB Output is correct
16 Correct 45 ms 11440 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 66 ms 17368 KB Output is correct
21 Correct 8 ms 2200 KB Output is correct
22 Correct 3 ms 1276 KB Output is correct
23 Correct 85 ms 21872 KB Output is correct
24 Correct 138 ms 36528 KB Output is correct
25 Correct 145 ms 37124 KB Output is correct
26 Correct 85 ms 19084 KB Output is correct
27 Correct 65 ms 15980 KB Output is correct
28 Correct 44 ms 9516 KB Output is correct
29 Correct 180 ms 65068 KB Output is correct
30 Correct 96 ms 35768 KB Output is correct
31 Correct 96 ms 35852 KB Output is correct
32 Correct 196 ms 58504 KB Output is correct
33 Correct 66 ms 17704 KB Output is correct
34 Correct 27 ms 6536 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 67540 KB Output is correct
2 Correct 659 ms 67560 KB Output is correct
3 Correct 606 ms 67672 KB Output is correct
4 Correct 605 ms 67572 KB Output is correct
5 Correct 618 ms 67532 KB Output is correct
6 Correct 633 ms 67660 KB Output is correct
7 Correct 619 ms 67668 KB Output is correct
8 Correct 628 ms 67568 KB Output is correct
9 Correct 611 ms 67660 KB Output is correct
10 Correct 627 ms 67640 KB Output is correct
11 Correct 613 ms 67556 KB Output is correct
12 Correct 585 ms 67568 KB Output is correct
13 Correct 591 ms 67572 KB Output is correct
14 Correct 597 ms 67688 KB Output is correct
15 Correct 604 ms 67776 KB Output is correct
16 Correct 615 ms 67532 KB Output is correct
17 Correct 631 ms 67516 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 6 ms 2172 KB Output is correct
20 Correct 2 ms 724 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 4 ms 1336 KB Output is correct
23 Correct 9 ms 2200 KB Output is correct
24 Correct 24 ms 5972 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 1 ms 480 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 37 ms 16348 KB Output is correct
29 Correct 24 ms 8504 KB Output is correct
30 Correct 22 ms 8188 KB Output is correct
31 Correct 42 ms 11404 KB Output is correct
32 Correct 1 ms 468 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 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 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 624 ms 67532 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 640 ms 67560 KB Output is correct
7 Correct 627 ms 67692 KB Output is correct
8 Correct 625 ms 67796 KB Output is correct
9 Correct 649 ms 67640 KB Output is correct
10 Correct 604 ms 67552 KB Output is correct
11 Correct 624 ms 67576 KB Output is correct
12 Correct 646 ms 67804 KB Output is correct
13 Correct 605 ms 67560 KB Output is correct
14 Correct 600 ms 67660 KB Output is correct
15 Correct 594 ms 67684 KB Output is correct
16 Correct 595 ms 67668 KB Output is correct
17 Correct 590 ms 67572 KB Output is correct
18 Correct 620 ms 67664 KB Output is correct
19 Correct 616 ms 67688 KB Output is correct
20 Correct 604 ms 67660 KB Output is correct
21 Correct 598 ms 67508 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 7 ms 2172 KB Output is correct
24 Correct 2 ms 724 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 5 ms 1316 KB Output is correct
27 Correct 9 ms 2212 KB Output is correct
28 Correct 25 ms 6024 KB Output is correct
29 Correct 2 ms 596 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 37 ms 16328 KB Output is correct
33 Correct 27 ms 8500 KB Output is correct
34 Correct 21 ms 8248 KB Output is correct
35 Correct 43 ms 11396 KB Output is correct
36 Correct 1 ms 468 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 63 ms 17372 KB Output is correct
40 Correct 8 ms 2200 KB Output is correct
41 Correct 3 ms 1276 KB Output is correct
42 Correct 91 ms 21828 KB Output is correct
43 Correct 139 ms 36652 KB Output is correct
44 Correct 152 ms 37184 KB Output is correct
45 Correct 81 ms 19104 KB Output is correct
46 Correct 73 ms 16048 KB Output is correct
47 Correct 47 ms 9380 KB Output is correct
48 Correct 188 ms 65080 KB Output is correct
49 Correct 96 ms 35792 KB Output is correct
50 Correct 93 ms 35780 KB Output is correct
51 Correct 191 ms 58568 KB Output is correct
52 Correct 63 ms 17616 KB Output is correct
53 Correct 26 ms 6452 KB Output is correct
54 Incorrect 1 ms 212 KB Output isn't correct
55 Halted 0 ms 0 KB -