#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
#include "hexagon.h"
const ll MOD = 1e9 + 7;
ll nr(ll x) {
x %= MOD;
x += MOD;
x %= MOD;
return x;
}
ll binpow(ll x, ll y) {
x = nr(x);
ll res = 1;
while (y > 0) {
if (y % 2 == 1)
res = nr(res * x);
x = nr(x * x);
y /= 2;
}
return res;
}
ll inv(ll x) {
return binpow(x, MOD - 2);
}
int dirX[6] = {0, 1, 1, 0, -1, -1};
int dirY[6] = {-1, 0, 1, 1, 0, -1};
int angle[6] = {0, 2, 3, 4, 6, 7};
vector<vi> turn = { {4, 2, 1, 0, 6, 5},
{6, 4, 3, 2, 0, 7},
{7, 5, 4, 3, 1, 0},
{0, 6, 5, 4, 2, 1},
{2, 0, 7, 6, 4, 3},
{3, 1, 0, 7, 5, 4}};
// counterclockwise turns
void precomp() {
}
int N;
ll A, B;
vi D, L;
int draw_territory(int N_g, int A_g, int B_g, vector<int> D_g, vector<int> L_g) {
N = N_g; A = A_g; B = B_g;
for (int x : D_g)
D.pb(x - 1);
for (int x : L_g)
L.pb(x);
vector<ii> pos;
pos.pb({0, 0});
for (int i = 0; i < N; i++) {
ll cx = pos.back().fi;
ll cy = pos.back().se;
cx += dirX[D[i]] * L[i];
cy += dirY[D[i]] * L[i];
pos.pb({cx, cy});
}
/* cout<<"pos: ";
for (ii p : pos)
cout<<"("<<p.fi<<", "<<p.se<<"); ";
cout<<endl;*/
int sum1 = 0; // counterclockwise sum
int sum2 = 0; // clockwise sum
for (int i = 0; i < N; i++) {
int diff = angle[D[(i + 1) % N]] - angle[D[i]];
if (diff != 0) {
if (diff < 0) { // counterclockwise turn
sum1 += -diff;
sum2 += (8 + diff);
}
else { // clockwise turn
sum1 += (8 - diff);
sum2 += diff;
}
}
}
// cout<<"sum1, sum2: "<<sum1<<" "<<sum2<<endl;
ll sl1 = 0; // shoelace, i <=> i+1
ll sl2 = 0; // shoelace, i+1 <=> i
for (int i = 0; i < N; i++) {
sl1 += nr(nr(pos[i].fi) * nr(pos[(i + 1) % N].se));
sl1 = nr(sl1);
sl2 += nr(nr(pos[i].se) * nr(pos[(i + 1) % N].fi));
sl2 = nr(sl2);
}
// need to know the direction
// cout<<"sl1, sl2: "<<sl1<<" "<<sl2<<endl;
ll total = nr((sl2 - sl1) * 4);
for (int i = 0; i < N; i++) {
total += nr((L[i] - 1) * 4);
total = nr(total);
int toadd = 0;
if (sum1 < sum2) // counterclockwise
toadd = turn[D[i]][D[(i + 1) % N]];
else // clockwise
toadd = 8 - turn[D[i]][D[(i + 1) % N]];
total += toadd;
total = nr(total);
}
// cout<<"total: "<<total<<endl;
return nr(A * nr(total * inv(8)));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1116 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
