QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#525254#7637. Exactly Three NeighborsJohnAlfnovAC ✓1ms3960kbC++142.1kb2024-08-20 15:02:542024-08-20 15:02:55

Judging History

你现在查看的是最新测评结果

  • [2024-08-20 15:02:55]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3960kb
  • [2024-08-20 15:02:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int v[105][105];
int n,m;
int gs=0,p,q;
mt19937 mt(1377);
void dfs(int x,int y){
	if(y>m){
		if(gs==n*m*p/q){
			int fl=1;
			for(int i=1;i<=n;++i){
				if(v[i][1]){
					int h=v[(i-2+n)%n+1][1]+v[i%n+1][1]+v[i][m]+v[i][2];
					if(h!=3)fl=0;
				}
				if(v[i][m]){
					int h=v[(i-2+n)%n+1][m]+v[i%n+1][m]+v[i][1]+v[i][m-1];
					if(h!=3)fl=0;
				}
			}
			if(fl){
				printf("%d %d\n",n,m);
				for(int i=1;i<=n;++i){
					for(int j=1;j<=m;++j){
						putchar(v[i][j]?'#':'.');
					}
					putchar('\n');
				}
				exit(0);
			}
		}
		return;
	}
	if(x==1){
		if(gs<0.7*(y-1)*n*p/q)return;
	}
	int o0=1,o1=1;
	if(y>2&&v[x][y-1]==1){
		int h=v[x][y-2]+v[(x-2+n)%n+1][y-1]+v[x%n+1][y-1];
		if(h==3)o1=0;
		else if(h==2)o0=0;
		else o0=o1=0;
	}
	if(x>1&&y>1&&v[x-1][y]&&!v[x-1][y-1])o0=0;
	if(x>2&&v[x-1][y]&&!v[x-2][y])o0=0;
	if(y>1&&v[x][y-1]&&(!v[(x-2+n)%n+1][y-1]||!v[x%n+1][y-1]))o0=0;
	if(x>1&&y>1&&!v[x-1][y]&&!v[x][y-1])o1=0;
	if(mt()%2==0){
		if(o0){
			v[x][y]=0;
			if(x==n)dfs(1,y+1);
			else dfs(x+1,y);
		}
		if(o1){
			v[x][y]=1;++gs;
			if(x==n)dfs(1,y+1);
			else dfs(x+1,y);
			--gs;
		}
	}else{
		if(o1){
			v[x][y]=1;++gs;
			if(x==n)dfs(1,y+1);
			else dfs(x+1,y);
			--gs;
		}
		if(o0){
			v[x][y]=0;
			if(x==n)dfs(1,y+1);
			else dfs(x+1,y);
		}
	}
}
int main(){
	scanf("%d%d",&p,&q);
	if(3*p<=2*q){
		if(p%2)p*=2,q*=2;
		printf("%d %d\n",1,q);
		for(int i=1;i<=q;++i){
			if(i%3!=0&&p)putchar('#'),--p;
			else putchar('.');
		}
		putchar('\n');
		return 0;
	}
	if(p==3&&q==4){
		puts("4 4");
		puts("..##");
		puts("####");
		puts("##..");
		puts("####");
		return 0;
	}
	if(p==4&&q==5){
		puts("5 5");
		puts(".####");
		puts("##.##");
		puts("####.");
		puts("#.###");
		puts("###.#");
		return 0;
	}
	if(p==5&&q==7){
		puts("6 7");
		puts(".###.##");
		puts("##.####");
		puts("##.##..");
		puts("##.##..");
		puts("##.####");
		puts(".###.##");
		return 0;
	}
	if(p==7&&q==9){
		n=6,m=18;
		dfs(1,1);
	}
	if(p==7&&q==10){
		n=10,m=12;
		dfs(1,1);
	}
	puts("-1 -1");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3924kb

input:

2 3

output:

1 3
##.

result:

ok good solution

Test #2:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

1 1

output:

-1 -1

result:

ok no solution

Test #3:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

3 4

output:

4 4
..##
####
##..
####

result:

ok good solution

Test #4:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

3 5

output:

1 10
##.##.##..

result:

ok good solution

Test #5:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

4 5

output:

5 5
.####
##.##
####.
#.###
###.#

result:

ok good solution

Test #6:

score: 0
Accepted
time: 0ms
memory: 3960kb

input:

7 10

output:

10 12
.##..#######
.##..##...##
.##..##...##
.##..#######
######.###.#
#..#####.###
####..##.##.
####..##.##.
#..#####.###
######.###.#

result:

ok good solution

Test #7:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

5 7

output:

6 7
.###.##
##.####
##.##..
##.##..
##.####
.###.##

result:

ok good solution

Test #8:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

7 9

output:

6 18
.##.####.####.####
.####.####.####.##
##.####.####.##.##
####.####.##.####.
#.####.##.####.###
###.##.####.####.#

result:

ok good solution

Test #9:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

0 1

output:

1 1
.

result:

ok good solution

Test #10:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

1 2

output:

1 4
##..

result:

ok good solution

Test #11:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

1 3

output:

1 6
##....

result:

ok good solution

Test #12:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

1 4

output:

1 8
##......

result:

ok good solution

Test #13:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

1 5

output:

1 10
##........

result:

ok good solution

Test #14:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

1 6

output:

1 12
##..........

result:

ok good solution

Test #15:

score: 0
Accepted
time: 0ms
memory: 3948kb

input:

1 7

output:

1 14
##............

result:

ok good solution

Test #16:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

1 8

output:

1 16
##..............

result:

ok good solution

Test #17:

score: 0
Accepted
time: 1ms
memory: 3812kb

input:

1 9

output:

1 18
##................

result:

ok good solution

Test #18:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

1 10

output:

1 20
##..................

result:

ok good solution

Test #19:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

2 5

output:

1 5
##...

result:

ok good solution

Test #20:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

2 7

output:

1 7
##.....

result:

ok good solution

Test #21:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

2 9

output:

1 9
##.......

result:

ok good solution

Test #22:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

3 7

output:

1 14
##.##.##......

result:

ok good solution

Test #23:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

3 8

output:

1 16
##.##.##........

result:

ok good solution

Test #24:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

3 10

output:

1 20
##.##.##............

result:

ok good solution

Test #25:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

4 7

output:

1 7
##.##..

result:

ok good solution

Test #26:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

4 9

output:

1 9
##.##....

result:

ok good solution

Test #27:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

5 6

output:

-1 -1

result:

ok no solution

Test #28:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

5 8

output:

1 16
##.##.##.##.##..

result:

ok good solution

Test #29:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

5 9

output:

1 18
##.##.##.##.##....

result:

ok good solution

Test #30:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

6 7

output:

-1 -1

result:

ok no solution

Test #31:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

7 8

output:

-1 -1

result:

ok no solution

Test #32:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

8 9

output:

-1 -1

result:

ok no solution

Test #33:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

9 10

output:

-1 -1

result:

ok no solution

Extra Test:

score: 0
Extra Test Passed