QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232179#7637. Exactly Three Neighborsucup-team1134AC ✓0ms3824kbC++177.9kb2023-10-29 23:02:282023-10-29 23:02:28

Judging History

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

  • [2023-10-29 23:02:28]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3824kb
  • [2023-10-29 23:02:28]
  • 提交

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;
    
}

詳細信息

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