QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #443000 | #7637. Exactly Three Neighbors | zwh2008 | AC ✓ | 0ms | 3724kb | C++14 | 2.1kb | 2024-06-15 14:02:02 | 2024-06-15 14:02:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;
#define fi first
#define se second
const int N=1e5+5;
int p,q,col[505][505];
bool chk(int j,int k,int a,int b){return !col[j][k]||col[(j+1)%a][k]+col[j][(k+1)%b]+col[(j-1+a)%a][k]+col[j][(k-1+b)%b]==3;}
void dfs(int x,int y,int a,int b,int k) {
if(x==a) {
for(int i=0;i<a;i++)for(int j=0;j<b;j++)if(!chk(i,j,a,b)||!chk(i,j,a,b))return;
cout<<a<<' '<<b<<"\\n";
for(int j=0;j<a;j++) {
for(int k=0;k<b;k++)cout<<(col[j][k]?'#':'.');
cout<<"\\n";
}
cout<<'\n';
cout<<a<<' '<<b<<"\n";
for(int j=0;j<a;j++) {
for(int k=0;k<b;k++)cout<<(col[j][k]?'#':'.');
cout<<"\n";
}
return void(cout<<'\n');
}
if((a-x)*b-y>k) {
col[x][y]=0;
if(x<2||chk(x-1,y,a,b))dfs(x+(y==b-1),(y+1)%b,a,b,k);
}
if(k) {
col[x][y]=1;
if(x<2||chk(x-1,y,a,b))dfs(x+(y==b-1),(y+1)%b,a,b,k-1);
}
col[x][y]=0;
}
int main() {
// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
// for(int p=0;p<=10;p++)for(int q=p;q<=10;q++)if(__gcd(p,q)==1&&3*p>2*q)cout<<p<<' '<<q<<'\n';
// return 0;
cin>>p>>q;
if(p==1&&q==1)cout<<"-1 -1",exit(0);
if(3*p<=2*q) {
if(p&1)p*=2,q*=2;
cout<<"1 "<<q<<'\n';
for(int i=1;i<=p/2;i++)cout<<"##.";
for(int i=1;i<=q-3*p/2;i++)cout<<'.';
return 0;
}
if(p==3&&q==4) {
cout<<"4 4\n####\n#..#\n####\n.##.\n";
return 0;
}
if(p==4&&q==5) {
cout<<"5 5\n#.###\n###.#\n.####\n##.##\n####.\n";
return 0;
}
if(p==7&&q==10) {
cout<<"5 4\n..##\n..##\n####\n##..\n####\n";
return 0;
}
if(p==5&&q==7) {
cout<<"7 6\n....##\n######\n####..\n#..###\n#..###\n####..\n######\n";
return 0;
}
if(p==7&&q==9) {
cout<<"18 6\n..####\n###.##\n#####.\n#..###\n####.#\n.#####\n##..##\n#####.\n#.####\n###..#\n.#####\n##.###\n####..\n#.####\n###.##\n.####.\n##.###\n####.#\n";
return 0;
}
cout<<"-1 -1\n";
return 0;
for(int s=q;s<=q*20;s+=q) {
for(int a=2;a*a<=s;a++)if(s%a==0) {
int b=s/a;
for(int i=0;i<b;i++)for(int j=0;j<a;j++)col[i][j]=0;
dfs(0,0,b,a,s/q*p);
}
}
return 0;
}
/*
3 4
4 5
5 6
5 7
6 7
7 8
7 9
7 10
8 9
9 10
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
2 3
output:
1 3 ##.
result:
ok good solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1 1
output:
-1 -1
result:
ok no solution
Test #3:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
3 4
output:
4 4 #### #..# #### .##.
result:
ok good solution
Test #4:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 5
output:
1 10 ##.##.##..
result:
ok good solution
Test #5:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
4 5
output:
5 5 #.### ###.# .#### ##.## ####.
result:
ok good solution
Test #6:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
7 10
output:
5 4 ..## ..## #### ##.. ####
result:
ok good solution
Test #7:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
5 7
output:
7 6 ....## ###### ####.. #..### #..### ####.. ######
result:
ok good solution
Test #8:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
7 9
output:
18 6 ..#### ###.## #####. #..### ####.# .##### ##..## #####. #.#### ###..# .##### ##.### ####.. #.#### ###.## .####. ##.### ####.#
result:
ok good solution
Test #9:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
0 1
output:
1 1 .
result:
ok good solution
Test #10:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
1 2
output:
1 4 ##..
result:
ok good solution
Test #11:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1 3
output:
1 6 ##....
result:
ok good solution
Test #12:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
1 4
output:
1 8 ##......
result:
ok good solution
Test #13:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1 5
output:
1 10 ##........
result:
ok good solution
Test #14:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1 6
output:
1 12 ##..........
result:
ok good solution
Test #15:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
1 7
output:
1 14 ##............
result:
ok good solution
Test #16:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1 8
output:
1 16 ##..............
result:
ok good solution
Test #17:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 9
output:
1 18 ##................
result:
ok good solution
Test #18:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1 10
output:
1 20 ##..................
result:
ok good solution
Test #19:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
2 5
output:
1 5 ##...
result:
ok good solution
Test #20:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2 7
output:
1 7 ##.....
result:
ok good solution
Test #21:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
2 9
output:
1 9 ##.......
result:
ok good solution
Test #22:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 7
output:
1 14 ##.##.##......
result:
ok good solution
Test #23:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
3 8
output:
1 16 ##.##.##........
result:
ok good solution
Test #24:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
3 10
output:
1 20 ##.##.##............
result:
ok good solution
Test #25:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
4 7
output:
1 7 ##.##..
result:
ok good solution
Test #26:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
4 9
output:
1 9 ##.##....
result:
ok good solution
Test #27:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
5 6
output:
-1 -1
result:
ok no solution
Test #28:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
5 8
output:
1 16 ##.##.##.##.##..
result:
ok good solution
Test #29:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
5 9
output:
1 18 ##.##.##.##.##....
result:
ok good solution
Test #30:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
6 7
output:
-1 -1
result:
ok no solution
Test #31:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
7 8
output:
-1 -1
result:
ok no solution
Test #32:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
8 9
output:
-1 -1
result:
ok no solution
Test #33:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
9 10
output:
-1 -1
result:
ok no solution
Extra Test:
score: 0
Extra Test Passed