Submission #434330

#	Time	Username	Problem	Language	Result	Execution time	Memory
434330		dqhungdl	Hexagonal Territory (APIO21_hexagon)	C++17	20 / 100	1182 ms	830948 KiB

hexagon

#include "hexagon.h"

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
const long long MOD=1e9+7,INC=2000;
int DD[4005][4005];
bool block[4005][4005],mark[4005][4005];

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+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;
	}
	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16