Submission #434330

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
434330	2021-06-21T00:50:35 Z	dqhungdl	Hexagonal Territory (APIO21_hexagon)	C++17	20 / 100	1182 ms	830948 KB

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.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	300 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct

Subtask #2
6.0 / 6.0

#	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	1 ms	296 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	300 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	1 ms	204 KB	Output is correct

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1182 ms	830612 KB	Output is correct
2	Correct	1055 ms	827848 KB	Output is correct
3	Correct	1053 ms	830088 KB	Output is correct
4	Correct	1084 ms	830540 KB	Output is correct
5	Correct	1114 ms	830584 KB	Output is correct
6	Correct	1051 ms	830812 KB	Output is correct
7	Correct	1092 ms	830556 KB	Output is correct
8	Correct	1106 ms	830692 KB	Output is correct
9	Correct	1069 ms	830684 KB	Output is correct
10	Correct	1075 ms	830668 KB	Output is correct
11	Correct	1071 ms	830440 KB	Output is correct
12	Correct	1060 ms	823412 KB	Output is correct
13	Correct	1036 ms	826344 KB	Output is correct
14	Correct	1120 ms	823288 KB	Output is correct
15	Correct	1082 ms	830404 KB	Output is correct
16	Correct	1073 ms	830776 KB	Output is correct
17	Correct	1070 ms	830472 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 15.0

#	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	Incorrect	1 ms	204 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1125 ms	830436 KB	Output is correct
2	Correct	1040 ms	827784 KB	Output is correct
3	Correct	1097 ms	830120 KB	Output is correct
4	Correct	1081 ms	830544 KB	Output is correct
5	Correct	1103 ms	830552 KB	Output is correct
6	Correct	1067 ms	830844 KB	Output is correct
7	Correct	1062 ms	830652 KB	Output is correct
8	Correct	1083 ms	830692 KB	Output is correct
9	Correct	1068 ms	830572 KB	Output is correct
10	Correct	1030 ms	830532 KB	Output is correct
11	Correct	1090 ms	830468 KB	Output is correct
12	Correct	1063 ms	823344 KB	Output is correct
13	Correct	1045 ms	826324 KB	Output is correct
14	Correct	1058 ms	823492 KB	Output is correct
15	Correct	1026 ms	830528 KB	Output is correct
16	Correct	1111 ms	830948 KB	Output is correct
17	Correct	1106 ms	830480 KB	Output is correct
18	Incorrect	1 ms	204 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #7
0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	1 ms	204 KB	Output is correct
5	Incorrect	1 ms	204 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #8
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1060 ms	830520 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	296 KB	Output is correct
6	Correct	1059 ms	827916 KB	Output is correct
7	Correct	1054 ms	830164 KB	Output is correct
8	Correct	1051 ms	830532 KB	Output is correct
9	Correct	1072 ms	830624 KB	Output is correct
10	Correct	1056 ms	830768 KB	Output is correct
11	Correct	1038 ms	830556 KB	Output is correct
12	Correct	1090 ms	830812 KB	Output is correct
13	Correct	1077 ms	830568 KB	Output is correct
14	Correct	1093 ms	830572 KB	Output is correct
15	Correct	1115 ms	830480 KB	Output is correct
16	Correct	1100 ms	823348 KB	Output is correct
17	Correct	1061 ms	826392 KB	Output is correct
18	Correct	1068 ms	823264 KB	Output is correct
19	Correct	1061 ms	830460 KB	Output is correct
20	Correct	1132 ms	830776 KB	Output is correct
21	Correct	1077 ms	830588 KB	Output is correct
22	Incorrect	1 ms	204 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Submission #434330

Compilation message