oj.uz

답안 #434330

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
434330 2021-06-21T00:50:35 Z dqhungdl 육각형 영역 (APIO21_hexagon) C++17
20 / 100
 1182 ms 830948 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -