#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef KAMIRULEZ
const bool local = true;
const int subtask = 5;
#else
const bool local = true;
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, {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 (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;
}
}
if (type == 1) {
S.erase(it);
}
}
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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
