#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const long long MOD=1e9+7,INC=2000;
int X[7]={0,0,1,1,0,-1,-1};
int Y[7]={0,1,1,0,-1,-1,0};
int DD[4005][4005];
bool block[4005][4005],mark[4005][4005];
void move(int &curX,int &curY,int d) {
curX+=X[d];
curY+=Y[d];
}
long long mult(long long x,long long k) {
if(k==0)
return 1;
long long tmp=mult(x,k/2);
if(k%2==0)
return tmp*tmp%MOD;
return tmp*tmp%MOD*x%MOD;
}
void dfs(int u,int v) {
mark[u][v]=true;
for(int d=1;d<=6;d++) {
int newU=u,newV=v;
move(newU,newV,d);
if(newU<0||newU>2*INC||newV<0||newV>2*INC||block[newU][newV]||mark[newU][newV])
continue;
dfs(newU,newV);
}
}
int draw_territory(int N, int A, int B,
std::vector<int> D, std::vector<int> L) {
if(N==3) {
long long l=L[0];
long long cnt=(l+1)*(l+2)%MOD*mult(2,MOD-2)%MOD;
long long dist=(l*(l+1)%MOD*mult(2,MOD-2)%MOD
+l*(l+1)%MOD*(2*l+1)%MOD*mult(6,MOD-2)%MOD)%MOD;
return (cnt*A+dist*B)%MOD;
} else if(accumulate(L.begin(),L.end(),0)<=2000) {
int curX=0,curY=0;
block[curX+INC][curY+INC]=true;
for(int i=0;i<N;i++)
while(L[i]--) {
move(curX,curY,D[i]);
block[curX+INC][curY+INC]=true;
}
dfs(0,0);
for(int i=0;i<=2*INC;i++)
for(int j=0;j<=2*INC;j++)
DD[i][j]=-1;
DD[INC][INC]=0;
queue<ii> Q;
Q.push({INC,INC});
while(!Q.empty()) {
int u=Q.front().first,v=Q.front().second;
Q.pop();
for(int d=1;d<=6;d++) {
int newU=u,newV=v;
move(newU,newV,d);
if(newU<0||newU>2*INC||newV<0||newV>2*INC||DD[newU][newV]!=-1||mark[newU][newV])
continue;
DD[newU][newV]=DD[u][v]+1;
Q.push({newU,newV});
}
}
long long cnt=0,dist=0;
for(int i=0;i<=2*INC;i++)
for(int j=0;j<=2*INC;j++)
if(!mark[i][j]) {
cnt++;
dist=(dist+DD[i][j])%MOD;
}
return (cnt*A+dist*B)%MOD;
} else if(B==0) {
// Pick's theorem
long long boundary=accumulate(L.begin(),L.end(),0);
vector<ii> segs;
segs.push_back({0,0});
for(int i=0;i<N;i++) {
int newX=segs.back().first+X[D[i]]*L[i];
int newY=segs.back().second+Y[D[i]]*L[i];
segs.push_back({newX,newY});
}
long long area=0;
for(int i=1;i<segs.size();i++)
area+=1LL*segs[i].first*segs[i-1].second-1LL*segs[i].second*segs[i-1].first;
area=abs(area);
long long inside=((area-boundary)/2+1)%MOD;
return (boundary+inside)*A%MOD;
}
return 0;
}
Compilation message
hexagon.cpp: In function 'int draw_territory(int, int, int, std::vector<int>, std::vector<int>)':
hexagon.cpp:92:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for(int i=1;i<segs.size();i++)
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1424 ms |
1048580 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
2 ms |
460 KB |
Output is correct |
6 |
Correct |
3 ms |
588 KB |
Output is correct |
7 |
Correct |
7 ms |
1100 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
12 ms |
1608 KB |
Output is correct |
12 |
Correct |
11 ms |
1720 KB |
Output is correct |
13 |
Correct |
10 ms |
1568 KB |
Output is correct |
14 |
Correct |
13 ms |
1736 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
9 ms |
1100 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
10 ms |
1736 KB |
Output is correct |
14 |
Correct |
11 ms |
1716 KB |
Output is correct |
15 |
Correct |
10 ms |
1608 KB |
Output is correct |
16 |
Correct |
11 ms |
1740 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
17 ms |
2628 KB |
Output is correct |
21 |
Correct |
2 ms |
588 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
23 ms |
3068 KB |
Output is correct |
24 |
Correct |
36 ms |
5104 KB |
Output is correct |
25 |
Correct |
37 ms |
5308 KB |
Output is correct |
26 |
Correct |
19 ms |
2748 KB |
Output is correct |
27 |
Correct |
18 ms |
1936 KB |
Output is correct |
28 |
Correct |
9 ms |
1608 KB |
Output is correct |
29 |
Correct |
40 ms |
5568 KB |
Output is correct |
30 |
Correct |
41 ms |
5588 KB |
Output is correct |
31 |
Correct |
53 ms |
5568 KB |
Output is correct |
32 |
Correct |
42 ms |
5576 KB |
Output is correct |
33 |
Correct |
27 ms |
2828 KB |
Output is correct |
34 |
Correct |
13 ms |
1704 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
0 ms |
204 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1285 ms |
1048580 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1285 ms |
1048580 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |