#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
class rad {
public:
ll a, b; // a + bsqrt(3)
rad() {}
rad(ll a, ll b) : a(a), b(b) {}
};
typedef pair<rad, rad> prr;
typedef pair<ll, ll> pii;
bool operator<(rad a, rad b) {
return pii(a.a, a.b) < pii(b.a, b.b);
}
rad operator+(rad a, rad b) {
return rad(a.a+b.a, a.b+b.b);
}
rad operator*(rad a, rad b) {
return rad(a.a*b.a+3*a.b*b.b, a.a*b.b+a.b*b.a);
}
// ll operator/(rad a, rad b) {
// assert(a.a/b.a == a.b/b.b); // probably good enough even though flooring
// return a.a/b.a;
// }
rad operator-(rad a, rad b) {
return rad(a.a-b.a, a.b-b.b);
}
rad operator*(prr a, prr b) { // cross product
return a.first*b.second-a.second*b.first;
}
prr operator+(prr a, prr b) {
return prr(a.first+b.first, a.second+b.second);
}
prr operator*(prr a, int b) {
return prr(a.first*rad(b, 0), a.second*rad(b, 0));
}
prr conv[6] = {prr(rad(0, 0), rad(2, 0)), prr(rad(0, 1), rad(1, 0)), prr(rad(0, 1), rad(-1, 0)),
prr(rad(0, 0), rad(-2, 0)), prr(rad(0, -1), rad(-1, 0)), prr(rad(0, -1), rad(1, 0)), };
map<prr, int> dist;
int dir(int d, bool cc) {
return (cc) ? (d+2)%6 : (d+4)%6;
}
int draw_territory(int n, int A, int B, vector<int> D, vector<int> L) {
// the distance between hex centers is 2 => base is 2/sqrt(3)
// => area is 6/sqrt(3) = 2sqrt(3)
// assert(B == 0);
prr cur(rad(0, 0), rad(0, 0));
rad sum(0, 0);
ll perim = 0;
for (int i = 0; i < n; i++) {
perim += L[i];
D[i]--;
prr nxt = cur+conv[D[i]]*L[i];
sum = sum+(cur*nxt);
cur = nxt;
}
assert(sum.a == 0);
bool cc = 1;
if (sum.b < 0) {
cc = 0;
sum.b = -sum.b;
}
sum = sum+rad(perim, 0)*rad(0, 2);
ll num_elems = 1+sum.b/4;
num_elems %= MOD;
ll ans = (A*num_elems)%MOD;
assert(cc);
for (int i = 0; i < n; i++) {
int s = dir(D[i], cc);
for (int j = 0; j < L[i]; j++) {
dist[cur+conv[s]] = -1;
cur = cur+conv[D[i]];
}
for (int j = s; j != dir(D[(i+1)%n], cc); j = (cc ? (j+5)%6 : (j+1)%6)) {
dist[cur+conv[j]] = -1;
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < L[i]; j++) {
// dist.erase(cur);
// cur = cur+conv[D[i]];
// }
// }
dist[cur] = 0;
queue<prr> q;
q.push(cur);
while (!q.empty()) {
prr tp = q.front();
q.pop();
ans += ((ll)B*dist[tp])%MOD;
ans %= MOD;
for (int i = 0; i < 6; i++) {
prr nxt = tp+conv[i];
if (dist.find(nxt) == dist.end()) {
dist[nxt] = 1+dist[tp];
q.push(nxt);
}
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2110 ms |
736516 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2105 ms |
764584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2069 ms |
171716 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2113 ms |
755912 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2093 ms |
775116 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
