oj.uz

Submission #434337

# Submission time Handle Problem Language Result Execution time Memory
434337 2021-06-21T01:31:09 Z dqhungdl Hexagonal Territory (APIO21_hexagon) C++17
47 / 100
 1339 ms 830932 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 X[]={0,0,1,1,0,-1,-1};
int Y[]={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) {
	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;
	} 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:102: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]
  102 |   for(int i=1;i<segs.size();i++)
      |               ~^~~~~~~~~~~~

Subtask #1
3.0 / 3.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 204 KB Output is correct
5 Correct 0 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 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1254 ms 830512 KB Output is correct
2 Correct 1196 ms 827792 KB Output is correct
3 Correct 1299 ms 830028 KB Output is correct
4 Correct 1234 ms 830596 KB Output is correct
5 Correct 1242 ms 830508 KB Output is correct
6 Correct 1277 ms 830740 KB Output is correct
7 Correct 1213 ms 830636 KB Output is correct
8 Correct 1339 ms 830700 KB Output is correct
9 Correct 1242 ms 830680 KB Output is correct
10 Correct 1186 ms 830656 KB Output is correct
11 Correct 1190 ms 830440 KB Output is correct
12 Correct 1200 ms 823344 KB Output is correct
13 Correct 1202 ms 826300 KB Output is correct
14 Correct 1255 ms 823264 KB Output is correct
15 Correct 1186 ms 830452 KB Output is correct
16 Correct 1220 ms 830672 KB Output is correct
17 Correct 1205 ms 830476 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct

Subtask #4
12.0 / 12.0

# 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 1 ms 460 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 7 ms 1200 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 10 ms 1608 KB Output is correct
12 Correct 10 ms 1608 KB Output is correct
13 Correct 10 ms 1608 KB Output is correct
14 Correct 11 ms 1760 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct

Subtask #5
15.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 Correct 1 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 2 ms 460 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 7 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 332 KB Output is correct
13 Correct 13 ms 1608 KB Output is correct
14 Correct 11 ms 1736 KB Output is correct
15 Correct 11 ms 1568 KB Output is correct
16 Correct 12 ms 1684 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 17 ms 2644 KB Output is correct
21 Correct 3 ms 588 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 28 ms 3096 KB Output is correct
24 Correct 37 ms 5176 KB Output is correct
25 Correct 47 ms 5308 KB Output is correct
26 Correct 19 ms 2748 KB Output is correct
27 Correct 13 ms 1820 KB Output is correct
28 Correct 10 ms 1608 KB Output is correct
29 Correct 41 ms 5556 KB Output is correct
30 Correct 52 ms 5556 KB Output is correct
31 Correct 40 ms 5572 KB Output is correct
32 Correct 41 ms 5568 KB Output is correct
33 Correct 20 ms 2884 KB Output is correct
34 Correct 11 ms 1712 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 1 ms 204 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1225 ms 830532 KB Output is correct
2 Correct 1177 ms 827828 KB Output is correct
3 Correct 1281 ms 830232 KB Output is correct
4 Correct 1205 ms 830680 KB Output is correct
5 Correct 1167 ms 830424 KB Output is correct
6 Correct 1209 ms 830932 KB Output is correct
7 Correct 1191 ms 830556 KB Output is correct
8 Correct 1195 ms 830696 KB Output is correct
9 Correct 1179 ms 830572 KB Output is correct
10 Correct 1248 ms 830572 KB Output is correct
11 Correct 1229 ms 830560 KB Output is correct
12 Correct 1157 ms 823344 KB Output is correct
13 Correct 1269 ms 826336 KB Output is correct
14 Correct 1176 ms 823300 KB Output is correct
15 Correct 1203 ms 830400 KB Output is correct
16 Correct 1269 ms 830776 KB Output is correct
17 Correct 1229 ms 830480 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 3 ms 460 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 7 ms 1228 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 10 ms 1864 KB Output is correct
29 Correct 13 ms 1864 KB Output is correct
30 Correct 10 ms 1840 KB Output is correct
31 Correct 11 ms 1956 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Incorrect 1 ms 204 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #7
0 / 18.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 0 ms 204 KB Output is correct
4 Correct 0 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 1239 ms 830580 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 Correct 1 ms 216 KB Output is correct
6 Correct 1277 ms 827760 KB Output is correct
7 Correct 1191 ms 830136 KB Output is correct
8 Correct 1272 ms 830540 KB Output is correct
9 Correct 1174 ms 830528 KB Output is correct
10 Correct 1180 ms 830736 KB Output is correct
11 Correct 1295 ms 830560 KB Output is correct
12 Correct 1223 ms 830696 KB Output is correct
13 Correct 1222 ms 830624 KB Output is correct
14 Correct 1227 ms 830664 KB Output is correct
15 Correct 1205 ms 830352 KB Output is correct
16 Correct 1198 ms 823468 KB Output is correct
17 Correct 1264 ms 826340 KB Output is correct
18 Correct 1241 ms 823204 KB Output is correct
19 Correct 1200 ms 830404 KB Output is correct
20 Correct 1201 ms 830776 KB Output is correct
21 Correct 1204 ms 830464 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 2 ms 588 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 3 ms 572 KB Output is correct
28 Correct 10 ms 1312 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 304 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 11 ms 1864 KB Output is correct
33 Correct 13 ms 1920 KB Output is correct
34 Correct 10 ms 1840 KB Output is correct
35 Correct 13 ms 1972 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 18 ms 3268 KB Output is correct
40 Correct 4 ms 692 KB Output is correct
41 Correct 2 ms 332 KB Output is correct
42 Correct 28 ms 3808 KB Output is correct
43 Correct 46 ms 6224 KB Output is correct
44 Correct 46 ms 6548 KB Output is correct
45 Correct 19 ms 3520 KB Output is correct
46 Correct 14 ms 2320 KB Output is correct
47 Correct 12 ms 1864 KB Output is correct
48 Correct 41 ms 6820 KB Output is correct
49 Correct 43 ms 6820 KB Output is correct
50 Correct 42 ms 6840 KB Output is correct
51 Correct 46 ms 6596 KB Output is correct
52 Correct 20 ms 3396 KB Output is correct
53 Correct 10 ms 1952 KB Output is correct
54 Incorrect 1 ms 204 KB Output isn't correct
55 Halted 0 ms 0 KB -