QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #232179 | #7637. Exactly Three Neighbors | ucup-team1134 | AC ✓ | 0ms | 3824kb | C++17 | 7.9kb | 2023-10-29 23:02:28 | 2023-10-29 23:02:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=1<<30;
vector<int> dh={0,1,0,-1},dw={1,0,-1,0};
int N=7,H=4,W=4;
char S[20][20];
void DFS(int h,int w,int cn){
//cout<<h<<" "<<w<<" "<<cn<<endl;
if(h==H){
bool ok=true;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(S[i][j]=='.') continue;
int cn=0;
for(int k=0;k<4;k++){
int toh=i+dh[k],tow=j+dw[k];
toh=(toh+H)%H;
tow=(tow+W)%W;
if(S[toh][tow]=='#') cn++;
}
if(cn!=3){
return;
}
}
}
int X=0;
for(int i=0;i<H;i++) for(int j=0;j<W;j++) if(S[i][j]=='#') X++;
if(ok&&X==H*W/2){
for(int i=0;i<H;i++){
cout<<S[i]<<"\n";
}
cout<<"\n";
}
return;
}
if(w==W){
if(1) DFS(h+1,0,0);
return;
}
if(1){
S[h][w]='#';
bool ok=true;
if(h>=2){
int i=h-1,j=w;
if(S[i][j]=='#'){
int cn=0;
for(int k=0;k<4;k++){
int toh=i+dh[k],tow=j+dw[k];
toh=(toh+H)%H;
tow=(tow+W)%W;
if(S[toh][tow]=='#') cn++;
}
if(cn!=3){
ok=false;
}
}
}
if(ok) DFS(h,w+1,cn+1);
}
if(1){
S[h][w]='.';
bool ok=true;
if(h>=2){
int i=h-1,j=w;
if(S[i][j]=='#'){
int cn=0;
for(int k=0;k<4;k++){
int toh=i+dh[k],tow=j+dw[k];
toh=(toh+H)%H;
tow=(tow+W)%W;
if(S[toh][tow]=='#') cn++;
}
if(cn!=3){
ok=false;
}
}
}
if(ok) DFS(h,w+1,cn);
}
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
// DFS(0,0,0);
/*
for(int i=0;i<18;i++){
cout<<"cout<<"<<'"';
string X;cin>>X;
cout<<X;
cout<<'\\';
cout<<'n';
cout<<'"';
cout<<';';
cout<<endl;
}
DFS(0,0,0);
return 0;
for(int H=7;H<=7;H++){
for(int W=H;W<=7;W++){
if((H*W)%7) continue;
vector<int> P(H*W);
for(int i=H*W/7*2;i<H*W;i++) P[i]=1;
do{
vector<string> S(H,string(W,'.'));
for(int i=0;i<H*W;i++){
if(P[i]) S[i/W][i%W]='#';
}
bool ok=true;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(S[i][j]=='.') continue;
int cn=0;
for(int k=0;k<4;k++){
int toh=i+dh[k],tow=j+dw[k];
toh=(toh+H)%H;
tow=(tow+W)%W;
if(S[toh][tow]=='#') cn++;
}
if(cn!=3){
ok=false;
break;
}
}
}
if(ok){
for(int i=0;i<H;i++){
cout<<S[i]<<"\n";
}
cout<<"\n";
}
}while(next_permutation(all(P)));
}
}
*/
int P,Q;cin>>P>>Q;
int H,W;
auto putX=[&](){
cout<<H<<" "<<W<<endl;
for(int j=0;j<W;j++){
if(j==0||j==W-1) cout<<'.';
else cout<<'#';
}
cout<<endl;
for(int j=0;j<W;j++){
if(j==0||j==1||j==W-2||j==W-1) cout<<'#';
else cout<<'.';
}
cout<<endl;
for(int j=0;j<W;j++){
if(j==0||j==1||j==W-2||j==W-1) cout<<'#';
else cout<<'.';
}
cout<<endl;
for(int j=0;j<W;j++){
if(j==0||j==W-1) cout<<'.';
else cout<<'#';
}
cout<<endl;
exit(0);
};
if(P==0){
cout<<1<<" "<<1<<endl;
cout<<'.'<<endl;
return 0;
}
if(P==1){
if(Q==1){
cout<<-1<<" "<<-1<<endl;
return 0;
}
if(Q==2){
cout<<4<<" "<<4<<endl;
cout<<"....\n";
cout<<"....\n";
cout<<"####\n";
cout<<"####\n";
return 0;
}
}
if(P==2){
if(Q==3){
H=4;W=6;
putX();
}
}
if(P==3){
if(Q==4){
cout<<4<<" "<<4<<endl;
cout<<"..##\n";
cout<<"####\n";
cout<<"##..\n";
cout<<"####\n";
return 0;
}
if(Q==5){
H=4;W=10;
putX();
}
}
if(P==4){
if(Q==5){
cout<<5<<" "<<5<<endl;
cout<<".####\n";
cout<<"##.##\n";
cout<<"####.\n";
cout<<"#.###\n";
cout<<"###.#\n";
return 0;
}
if(Q==7){
H=4;W=14;
putX();
}
}
if(P==5){
if(Q==7){
cout<<10<<" "<<7<<endl;
cout<<"#######\n";
cout<<"####...\n";
cout<<"#..####\n";
cout<<"#..####\n";
cout<<"####...\n";
cout<<"#######\n";
cout<<"....###\n";
cout<<"#####.#\n";
cout<<"#####.#\n";
cout<<"....###\n";
return 0;
}
if(Q==8){
H=4;W=8;
putX();
}
if(Q==9){
H=4;W=18;
putX();
}
}
if(P==7){
if(Q==9){
cout<<18<<" "<<6<<endl;
cout<<"#####.\n";
cout<<"###.##\n";
cout<<"..####\n";
cout<<"####.#\n";
cout<<"##.###\n";
cout<<".####.\n";
cout<<"###.##\n";
cout<<"#.####\n";
cout<<"####..\n";
cout<<"##.###\n";
cout<<".#####\n";
cout<<"###..#\n";
cout<<"#.####\n";
cout<<"#####.\n";
cout<<"##..##\n";
cout<<".#####\n";
cout<<"####.#\n";
cout<<"#..###\n";
return 0;
}
if(Q==10){
H=4;W=5;
putX();
}
}
if(3*P<=2*Q){
cout<<2*Q<<" "<<4<<endl;
for(int i=0;i<P;i++){
cout<<"####\n";
cout<<"####\n";
cout<<"....\n";
}
for(int i=0;i<2*(Q-P)-P;i++){
cout<<"....\n";
}
return 0;
}
if((2*Q)%P==0){
int X=2*Q/P;
cout<<X<<" "<<4<<endl;
for(int i=0;i<2;i++) cout<<"####\n";
for(int i=0;i<X-2;i++) cout<<"....\n";
return 0;
}
cout<<-1<<" "<<-1<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3744kb
input:
2 3
output:
4 6 .####. ##..## ##..## .####.
result:
ok good solution
Test #2:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
1 1
output:
-1 -1
result:
ok no solution
Test #3:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 4
output:
4 4 ..## #### ##.. ####
result:
ok good solution
Test #4:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
3 5
output:
4 10 .########. ##......## ##......## .########.
result:
ok good solution
Test #5:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
4 5
output:
5 5 .#### ##.## ####. #.### ###.#
result:
ok good solution
Test #6:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
7 10
output:
4 5 .###. ##.## ##.## .###.
result:
ok good solution
Test #7:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5 7
output:
10 7 ####### ####... #..#### #..#### ####... ####### ....### #####.# #####.# ....###
result:
ok good solution
Test #8:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
7 9
output:
18 6 #####. ###.## ..#### ####.# ##.### .####. ###.## #.#### ####.. ##.### .##### ###..# #.#### #####. ##..## .##### ####.# #..###
result:
ok good solution
Test #9:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
0 1
output:
1 1 .
result:
ok good solution
Test #10:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
1 2
output:
4 4 .... .... #### ####
result:
ok good solution
Test #11:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
1 3
output:
6 4 #### #### .... .... .... ....
result:
ok good solution
Test #12:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
1 4
output:
8 4 #### #### .... .... .... .... .... ....
result:
ok good solution
Test #13:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 5
output:
10 4 #### #### .... .... .... .... .... .... .... ....
result:
ok good solution
Test #14:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
1 6
output:
12 4 #### #### .... .... .... .... .... .... .... .... .... ....
result:
ok good solution
Test #15:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 7
output:
14 4 #### #### .... .... .... .... .... .... .... .... .... .... .... ....
result:
ok good solution
Test #16:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
1 8
output:
16 4 #### #### .... .... .... .... .... .... .... .... .... .... .... .... .... ....
result:
ok good solution
Test #17:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
1 9
output:
18 4 #### #### .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ....
result:
ok good solution
Test #18:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
1 10
output:
20 4 #### #### .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ....
result:
ok good solution
Test #19:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
2 5
output:
10 4 #### #### .... #### #### .... .... .... .... ....
result:
ok good solution
Test #20:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
2 7
output:
14 4 #### #### .... #### #### .... .... .... .... .... .... .... .... ....
result:
ok good solution
Test #21:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
2 9
output:
18 4 #### #### .... #### #### .... .... .... .... .... .... .... .... .... .... .... .... ....
result:
ok good solution
Test #22:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
3 7
output:
14 4 #### #### .... #### #### .... #### #### .... .... .... .... .... ....
result:
ok good solution
Test #23:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
3 8
output:
16 4 #### #### .... #### #### .... #### #### .... .... .... .... .... .... .... ....
result:
ok good solution
Test #24:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
3 10
output:
20 4 #### #### .... #### #### .... #### #### .... .... .... .... .... .... .... .... .... .... .... ....
result:
ok good solution
Test #25:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
4 7
output:
4 14 .############. ##..........## ##..........## .############.
result:
ok good solution
Test #26:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
4 9
output:
18 4 #### #### .... #### #### .... #### #### .... #### #### .... .... .... .... .... .... ....
result:
ok good solution
Test #27:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
5 6
output:
-1 -1
result:
ok no solution
Test #28:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
5 8
output:
4 8 .######. ##....## ##....## .######.
result:
ok good solution
Test #29:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
5 9
output:
4 18 .################. ##..............## ##..............## .################.
result:
ok good solution
Test #30:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
6 7
output:
-1 -1
result:
ok no solution
Test #31:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
7 8
output:
-1 -1
result:
ok no solution
Test #32:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
8 9
output:
-1 -1
result:
ok no solution
Test #33:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
9 10
output:
-1 -1
result:
ok no solution
Extra Test:
score: 0
Extra Test Passed