oj.uz

Submission #727785

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

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;
					}
				}
			}
		}
	}
	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 0 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 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 606 ms 67544 KB Output is correct
2 Correct 578 ms 67676 KB Output is correct
3 Correct 575 ms 67560 KB Output is correct
4 Correct 587 ms 67664 KB Output is correct
5 Correct 588 ms 67560 KB Output is correct
6 Correct 577 ms 67564 KB Output is correct
7 Correct 591 ms 67560 KB Output is correct
8 Correct 581 ms 67548 KB Output is correct
9 Correct 587 ms 67552 KB Output is correct
10 Correct 572 ms 67564 KB Output is correct
11 Correct 570 ms 67648 KB Output is correct
12 Correct 583 ms 67672 KB Output is correct
13 Correct 624 ms 67564 KB Output is correct
14 Correct 607 ms 67692 KB Output is correct
15 Correct 595 ms 67544 KB Output is correct
16 Correct 574 ms 67760 KB Output is correct
17 Correct 574 ms 67564 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 5 ms 2172 KB Output is correct
3 Correct 2 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 8 ms 2248 KB Output is correct
7 Correct 20 ms 6028 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 32 ms 16332 KB Output is correct
12 Correct 21 ms 8532 KB Output is correct
13 Correct 19 ms 8248 KB Output is correct
14 Correct 51 ms 11400 KB Output is correct
15 Correct 1 ms 468 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 6 ms 2172 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 4 ms 1336 KB Output is correct
8 Correct 6 ms 2200 KB Output is correct
9 Correct 21 ms 6032 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 38 ms 16244 KB Output is correct
14 Correct 30 ms 8472 KB Output is correct
15 Correct 17 ms 8204 KB Output is correct
16 Correct 39 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 57 ms 17472 KB Output is correct
21 Correct 6 ms 2096 KB Output is correct
22 Correct 3 ms 1276 KB Output is correct
23 Correct 74 ms 21864 KB Output is correct
24 Correct 118 ms 36528 KB Output is correct
25 Correct 129 ms 37184 KB Output is correct
26 Correct 71 ms 19128 KB Output is correct
27 Correct 54 ms 15984 KB Output is correct
28 Correct 36 ms 9436 KB Output is correct
29 Correct 152 ms 65068 KB Output is correct
30 Correct 84 ms 35768 KB Output is correct
31 Correct 81 ms 35844 KB Output is correct
32 Correct 168 ms 58544 KB Output is correct
33 Correct 56 ms 17676 KB Output is correct
34 Correct 21 ms 6460 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 0 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 616 ms 67768 KB Output is correct
2 Correct 591 ms 67680 KB Output is correct
3 Correct 583 ms 67544 KB Output is correct
4 Correct 589 ms 67660 KB Output is correct
5 Correct 593 ms 67636 KB Output is correct
6 Correct 584 ms 67804 KB Output is correct
7 Correct 583 ms 67680 KB Output is correct
8 Correct 580 ms 67668 KB Output is correct
9 Correct 580 ms 67556 KB Output is correct
10 Correct 601 ms 67560 KB Output is correct
11 Correct 602 ms 67680 KB Output is correct
12 Correct 598 ms 67560 KB Output is correct
13 Correct 589 ms 67672 KB Output is correct
14 Correct 586 ms 67624 KB Output is correct
15 Correct 584 ms 67564 KB Output is correct
16 Correct 588 ms 67516 KB Output is correct
17 Correct 577 ms 67648 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 5 ms 2160 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 1260 KB Output is correct
23 Correct 6 ms 2200 KB Output is correct
24 Correct 20 ms 6024 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 33 ms 16324 KB Output is correct
29 Correct 20 ms 8504 KB Output is correct
30 Correct 18 ms 8188 KB Output is correct
31 Correct 35 ms 11420 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 0 ms 212 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 600 ms 67552 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 1 ms 212 KB Output is correct
6 Correct 576 ms 67644 KB Output is correct
7 Correct 581 ms 67656 KB Output is correct
8 Correct 575 ms 67564 KB Output is correct
9 Correct 581 ms 67592 KB Output is correct
10 Correct 594 ms 67660 KB Output is correct
11 Correct 577 ms 67516 KB Output is correct
12 Correct 581 ms 67660 KB Output is correct
13 Correct 579 ms 67644 KB Output is correct
14 Correct 571 ms 67680 KB Output is correct
15 Correct 585 ms 67592 KB Output is correct
16 Correct 583 ms 67660 KB Output is correct
17 Correct 577 ms 67572 KB Output is correct
18 Correct 575 ms 67560 KB Output is correct
19 Correct 569 ms 67784 KB Output is correct
20 Correct 591 ms 67668 KB Output is correct
21 Correct 576 ms 67628 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 6 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 3 ms 1316 KB Output is correct
27 Correct 6 ms 2200 KB Output is correct
28 Correct 20 ms 6020 KB Output is correct
29 Correct 1 ms 608 KB Output is correct
30 Correct 1 ms 480 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 31 ms 16308 KB Output is correct
33 Correct 21 ms 8504 KB Output is correct
34 Correct 17 ms 8264 KB Output is correct
35 Correct 35 ms 11448 KB Output is correct
36 Correct 1 ms 468 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 51 ms 17468 KB Output is correct
40 Correct 5 ms 2200 KB Output is correct
41 Correct 3 ms 1276 KB Output is correct
42 Correct 66 ms 21876 KB Output is correct
43 Correct 114 ms 36556 KB Output is correct
44 Correct 114 ms 37104 KB Output is correct
45 Correct 66 ms 19100 KB Output is correct
46 Correct 58 ms 15904 KB Output is correct
47 Correct 33 ms 9380 KB Output is correct
48 Correct 143 ms 65080 KB Output is correct
49 Correct 77 ms 35812 KB Output is correct
50 Correct 77 ms 35776 KB Output is correct
51 Correct 164 ms 58576 KB Output is correct
52 Correct 53 ms 17672 KB Output is correct
53 Correct 21 ms 6504 KB Output is correct
54 Incorrect 0 ms 212 KB Output isn't correct
55 Halted 0 ms 0 KB -