oj.uz

Submission #727287

# Submission time Handle Problem Language Result Execution time Memory
727287 2023-04-20T11:13:31 Z SanguineChameleon Hexagonal Territory (APIO21_hexagon) C++17
47 / 100
 736 ms 67912 KB 
#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef KAMIRULEZ
	const bool local = true;
	const int subtask = 8;
#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): type(_type) {};

	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);
		}
	}
};

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) {
	if (L1.type == -1) {
		return true;
	}
	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;
	}
};

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, lines.size());
			}
		}
		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());
			}
		}
	}
	if (B == 0 && (!local || subtask == 4 || subtask == 5)) {
		long long res = 0;
		for (auto L: lines) {
			res += L.calc();
			res %= mod;
		}
		if (res < 0) {
			res += mod;
		}
		res = res * A % mod;
		return res;
	}
	return 0;
/*	vector<pair<int, pair<int, line>>> events;
	for (auto L: lines) {
		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;
	line prv_top(-1);
	for (auto e: events) {
		int cur_x = e.first;
		int type = e.second.first;
		line L = e.second.second;
		if (type == 0) {
			prv_top = line(-1);
			S.insert(L);
		}
		else {
			auto it = S.lower_bound(L);
			if (it->type == 1 && next(it) != S.end() && next(it)->type == 2 && next(it)->p2.x > cur_x && prv_top < *it)  {
				cout << "match" << " " << (*it) << " " << (*next(it)) << " " << cur_x << '\n';
				cout << '\n';
				prv_top = *next(it);
			}
			if (it->type == 2 && it != S.begin() && prev(it)->type == 1 && prv_top < *prev(it))  {
				cout << "match" << " " << (*prev(it)) << " " << (*it) << " " << cur_x << '\n';
				cout << '\n';
				prv_top = *it;
			}
			S.erase(it);
		}
		for (auto L: S) {
			cout << L << '\n';
		}
		cout << '\n';
	}*/
	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:54:2: warning:   when initialized here [-Wreorder]
   54 |  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:59:13: warning: unused variable 'res' [-Wunused-variable]
   59 |   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 1 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 1 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 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 679 ms 67684 KB Output is correct
2 Correct 736 ms 67656 KB Output is correct
3 Correct 638 ms 67668 KB Output is correct
4 Correct 628 ms 67656 KB Output is correct
5 Correct 691 ms 67512 KB Output is correct
6 Correct 637 ms 67608 KB Output is correct
7 Correct 656 ms 67548 KB Output is correct
8 Correct 680 ms 67792 KB Output is correct
9 Correct 659 ms 67684 KB Output is correct
10 Correct 704 ms 67564 KB Output is correct
11 Correct 643 ms 67560 KB Output is correct
12 Correct 726 ms 67520 KB Output is correct
13 Correct 654 ms 67800 KB Output is correct
14 Correct 633 ms 67688 KB Output is correct
15 Correct 658 ms 67644 KB Output is correct
16 Correct 665 ms 67560 KB Output is correct
17 Correct 657 ms 67552 KB Output is correct
18 Correct 0 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 0 ms 212 KB Output is correct
2 Correct 2 ms 1048 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 740 KB Output is correct
6 Correct 2 ms 1044 KB Output is correct
7 Correct 8 ms 3020 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 11 ms 5224 KB Output is correct
12 Correct 11 ms 3704 KB Output is correct
13 Correct 9 ms 3596 KB Output is correct
14 Correct 11 ms 5296 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 296 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 212 KB Output is correct
4 Correct 2 ms 1048 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 2 ms 764 KB Output is correct
8 Correct 2 ms 1140 KB Output is correct
9 Correct 8 ms 3020 KB Output is correct
10 Correct 1 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 5220 KB Output is correct
14 Correct 10 ms 3752 KB Output is correct
15 Correct 10 ms 3532 KB Output is correct
16 Correct 11 ms 5320 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 300 KB Output is correct
20 Correct 19 ms 6208 KB Output is correct
21 Correct 3 ms 1172 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 25 ms 10720 KB Output is correct
24 Correct 39 ms 13116 KB Output is correct
25 Correct 43 ms 13456 KB Output is correct
26 Correct 18 ms 6872 KB Output is correct
27 Correct 13 ms 5876 KB Output is correct
28 Correct 9 ms 3660 KB Output is correct
29 Correct 44 ms 20268 KB Output is correct
30 Correct 40 ms 14124 KB Output is correct
31 Correct 44 ms 14112 KB Output is correct
32 Correct 46 ms 20008 KB Output is correct
33 Correct 19 ms 6984 KB Output is correct
34 Correct 11 ms 3604 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 296 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 67912 KB Output is correct
2 Correct 628 ms 67672 KB Output is correct
3 Correct 602 ms 67516 KB Output is correct
4 Correct 599 ms 67556 KB Output is correct
5 Correct 607 ms 67688 KB Output is correct
6 Correct 618 ms 67684 KB Output is correct
7 Correct 676 ms 67660 KB Output is correct
8 Correct 719 ms 67656 KB Output is correct
9 Correct 595 ms 67532 KB Output is correct
10 Correct 612 ms 67792 KB Output is correct
11 Correct 610 ms 67564 KB Output is correct
12 Correct 602 ms 67560 KB Output is correct
13 Correct 627 ms 67792 KB Output is correct
14 Correct 582 ms 67692 KB Output is correct
15 Correct 643 ms 67576 KB Output is correct
16 Correct 601 ms 67784 KB Output is correct
17 Correct 613 ms 67660 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 2 ms 1048 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 4 ms 1116 KB Output is correct
24 Correct 7 ms 3020 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 12 ms 5192 KB Output is correct
29 Correct 12 ms 3660 KB Output is correct
30 Correct 9 ms 3532 KB Output is correct
31 Correct 11 ms 5296 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 300 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 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 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 605 ms 67664 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 597 ms 67684 KB Output is correct
7 Correct 639 ms 67792 KB Output is correct
8 Correct 619 ms 67532 KB Output is correct
9 Correct 620 ms 67552 KB Output is correct
10 Correct 615 ms 67652 KB Output is correct
11 Correct 650 ms 67560 KB Output is correct
12 Correct 618 ms 67532 KB Output is correct
13 Correct 597 ms 67556 KB Output is correct
14 Correct 592 ms 67616 KB Output is correct
15 Correct 638 ms 67560 KB Output is correct
16 Correct 639 ms 67560 KB Output is correct
17 Correct 611 ms 67556 KB Output is correct
18 Correct 628 ms 67552 KB Output is correct
19 Correct 609 ms 67640 KB Output is correct
20 Correct 624 ms 67776 KB Output is correct
21 Correct 635 ms 67508 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 2 ms 1076 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 308 KB Output is correct
26 Correct 2 ms 764 KB Output is correct
27 Correct 2 ms 1044 KB Output is correct
28 Correct 8 ms 3020 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 11 ms 5156 KB Output is correct
33 Correct 10 ms 3660 KB Output is correct
34 Correct 11 ms 3540 KB Output is correct
35 Correct 12 ms 5296 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 304 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 19 ms 6164 KB Output is correct
40 Correct 3 ms 1044 KB Output is correct
41 Correct 1 ms 724 KB Output is correct
42 Correct 25 ms 10684 KB Output is correct
43 Correct 39 ms 13012 KB Output is correct
44 Correct 39 ms 13500 KB Output is correct
45 Correct 18 ms 6868 KB Output is correct
46 Correct 14 ms 5928 KB Output is correct
47 Correct 10 ms 3636 KB Output is correct
48 Correct 45 ms 20280 KB Output is correct
49 Correct 47 ms 14112 KB Output is correct
50 Correct 41 ms 14112 KB Output is correct
51 Correct 45 ms 19936 KB Output is correct
52 Correct 21 ms 6984 KB Output is correct
53 Correct 11 ms 3708 KB Output is correct
54 Incorrect 1 ms 212 KB Output isn't correct
55 Halted 0 ms 0 KB -