This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const long long MOD=1e9+7,INC=1500;
int DD[3005][3005];
bool block[3005][3005],mark[3005][3005];
void move(int &curX,int &curY,int d) {
if(d==1)
curY++;
else if(d==2)
curX++,curY++;
else if(d==3)
curX++;
else if(d==4)
curY--;
else if(d==5)
curX--,curY--;
else
curX--;
}
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*(l+1)%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;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |