oj.uz

Submission #954200

# Submission time Handle Problem Language Result Execution time Memory
954200 2024-03-27T11:41:17 Z Trisanu_Das Hexagonal Territory (APIO21_hexagon) C++17
47 / 100
 1232 ms 833616 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 592 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1139 ms 832508 KB Output is correct
2 Correct 887 ms 828588 KB Output is correct
3 Correct 945 ms 831828 KB Output is correct
4 Correct 938 ms 832024 KB Output is correct
5 Correct 923 ms 833616 KB Output is correct
6 Correct 915 ms 832084 KB Output is correct
7 Correct 977 ms 831640 KB Output is correct
8 Correct 919 ms 832336 KB Output is correct
9 Correct 965 ms 832520 KB Output is correct
10 Correct 948 ms 832452 KB Output is correct
11 Correct 959 ms 832132 KB Output is correct
12 Correct 884 ms 825692 KB Output is correct
13 Correct 868 ms 828496 KB Output is correct
14 Correct 929 ms 825172 KB Output is correct
15 Correct 972 ms 832596 KB Output is correct
16 Correct 913 ms 832596 KB Output is correct
17 Correct 925 ms 832336 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 5 ms 1332 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 7 ms 1728 KB Output is correct
12 Correct 7 ms 1752 KB Output is correct
13 Correct 6 ms 1708 KB Output is correct
14 Correct 7 ms 1748 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 4 ms 1240 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 7 ms 1752 KB Output is correct
14 Correct 7 ms 1752 KB Output is correct
15 Correct 6 ms 1748 KB Output is correct
16 Correct 8 ms 1760 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 11 ms 2728 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 19 ms 3280 KB Output is correct
24 Correct 25 ms 5328 KB Output is correct
25 Correct 25 ms 5328 KB Output is correct
26 Correct 13 ms 3024 KB Output is correct
27 Correct 9 ms 2004 KB Output is correct
28 Correct 7 ms 1752 KB Output is correct
29 Correct 28 ms 5572 KB Output is correct
30 Correct 28 ms 5584 KB Output is correct
31 Correct 28 ms 5580 KB Output is correct
32 Correct 28 ms 5584 KB Output is correct
33 Correct 13 ms 3024 KB Output is correct
34 Correct 7 ms 1752 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 832708 KB Output is correct
2 Correct 905 ms 828756 KB Output is correct
3 Correct 892 ms 831824 KB Output is correct
4 Correct 929 ms 831896 KB Output is correct
5 Correct 922 ms 833476 KB Output is correct
6 Correct 910 ms 832300 KB Output is correct
7 Correct 922 ms 831664 KB Output is correct
8 Correct 922 ms 832216 KB Output is correct
9 Correct 931 ms 832528 KB Output is correct
10 Correct 973 ms 832592 KB Output is correct
11 Correct 905 ms 832340 KB Output is correct
12 Correct 905 ms 825520 KB Output is correct
13 Correct 893 ms 828556 KB Output is correct
14 Correct 901 ms 825292 KB Output is correct
15 Correct 961 ms 832556 KB Output is correct
16 Correct 883 ms 832360 KB Output is correct
17 Correct 904 ms 832340 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 2 ms 604 KB Output is correct
24 Correct 5 ms 1456 KB Output is correct
25 Correct 1 ms 548 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 7 ms 1924 KB Output is correct
29 Correct 7 ms 2008 KB Output is correct
30 Correct 6 ms 2008 KB Output is correct
31 Correct 7 ms 2008 KB Output is correct
32 Correct 1 ms 452 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Incorrect 0 ms 348 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 874 ms 832624 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 895 ms 828608 KB Output is correct
7 Correct 888 ms 831828 KB Output is correct
8 Correct 924 ms 831892 KB Output is correct
9 Correct 913 ms 833448 KB Output is correct
10 Correct 928 ms 832260 KB Output is correct
11 Correct 931 ms 831640 KB Output is correct
12 Correct 924 ms 832076 KB Output is correct
13 Correct 910 ms 832396 KB Output is correct
14 Correct 906 ms 832472 KB Output is correct
15 Correct 896 ms 832080 KB Output is correct
16 Correct 919 ms 825696 KB Output is correct
17 Correct 910 ms 828592 KB Output is correct
18 Correct 922 ms 825172 KB Output is correct
19 Correct 969 ms 832540 KB Output is correct
20 Correct 1232 ms 832532 KB Output is correct
21 Correct 917 ms 832376 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 2 ms 808 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 2 ms 812 KB Output is correct
28 Correct 5 ms 1464 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 448 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 7 ms 2008 KB Output is correct
33 Correct 7 ms 2008 KB Output is correct
34 Correct 7 ms 1856 KB Output is correct
35 Correct 8 ms 2008 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 452 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 12 ms 3228 KB Output is correct
40 Correct 2 ms 860 KB Output is correct
41 Correct 1 ms 376 KB Output is correct
42 Correct 16 ms 4052 KB Output is correct
43 Correct 25 ms 6356 KB Output is correct
44 Correct 27 ms 6600 KB Output is correct
45 Correct 14 ms 3540 KB Output is correct
46 Correct 12 ms 2344 KB Output is correct
47 Correct 7 ms 2008 KB Output is correct
48 Correct 29 ms 7048 KB Output is correct
49 Correct 28 ms 6856 KB Output is correct
50 Correct 32 ms 6856 KB Output is correct
51 Correct 29 ms 6596 KB Output is correct
52 Correct 14 ms 3396 KB Output is correct
53 Correct 8 ms 2008 KB Output is correct
54 Incorrect 1 ms 348 KB Output isn't correct
55 Halted 0 ms 0 KB -