#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(perim <= 2000);
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]];
}
if ((cc && D[(i+1)%n] == (D[i]+1)%6) || (!cc && D[i] == ((D[(i+1)%n])+1)%6)) continue;
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]];
}
}
// cerr << dist.size() << "\n";
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 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
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 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
48 ms |
4404 KB |
Output is correct |
3 |
Correct |
17 ms |
1848 KB |
Output is correct |
4 |
Correct |
6 ms |
852 KB |
Output is correct |
5 |
Correct |
3 ms |
596 KB |
Output is correct |
6 |
Correct |
2 ms |
596 KB |
Output is correct |
7 |
Correct |
10 ms |
1324 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
432 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
4 ms |
808 KB |
Output is correct |
12 |
Correct |
152 ms |
10664 KB |
Output is correct |
13 |
Correct |
117 ms |
10584 KB |
Output is correct |
14 |
Correct |
133 ms |
11888 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
242 ms |
17812 KB |
Output is correct |
19 |
Correct |
214 ms |
17236 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
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 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
47 ms |
4412 KB |
Output is correct |
3 |
Correct |
17 ms |
1896 KB |
Output is correct |
4 |
Correct |
6 ms |
852 KB |
Output is correct |
5 |
Correct |
3 ms |
664 KB |
Output is correct |
6 |
Correct |
3 ms |
596 KB |
Output is correct |
7 |
Correct |
10 ms |
1280 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
3 ms |
408 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
5 ms |
852 KB |
Output is correct |
12 |
Correct |
129 ms |
10704 KB |
Output is correct |
13 |
Correct |
120 ms |
10524 KB |
Output is correct |
14 |
Correct |
129 ms |
11844 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
19 |
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 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
3 |
Halted |
0 ms |
0 KB |
- |