QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#498395#9164. Toybachbeo20070 1ms8276kbC++232.3kb2024-07-30 13:34:462024-07-30 13:34:47

Judging History

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

  • [2024-07-30 13:34:47]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:8276kb
  • [2024-07-30 13:34:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1505;
#define pii pair<int,int>
#define fi first
#define se second
int dx[]={0,0,-1,1},
    dy[]={-1,1,0,0};

int N,M,K,L,X,Y,U,V,_;
int c[maxn][maxn],d[maxn][maxn];
int lt[2][maxn][maxn],up[2][maxn][maxn];

bool out(int x,int y){
    return (x<=0 || y<=0 || x>N || y>M);
}

bool query(int x,int y,int u,int v){
    if(out(x,y) || out(u,v)) return true;
    return c[u][v]-c[x-1][v]-c[u][y-1]+c[x-1][y-1];
}

bool check(int x,int y,int u,int v){
    if(x>u || y>v) swap(x,u),swap(y,v);
    if(query(x,y,u,v)) return false;
    if(y+1==v){
        int p=max(up[1][x][y],x-L)+1;
        if(query(p,y,p+L-1,y+1)) return false;
        p=max(lt[0][x][y],y-K+1)+1;
        if(query(x,p,x,p+K-1)) return false;
    }
    else if(x+1==u){
        int p=max(lt[1][x][y],y-K)+1;
        if(query(x,p,x+1,p+K-1)) return false;
        p=max(up[0][x][y],x-L+1)+1;
        if(query(p,y,p+L-1,y)) return false;
    }
    return true;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> M >> N >> K >> L;
    cin >> _ >> X >> Y >> _;X++;Y++;
    for(int i=1;i<=N;i++) for(int j=1;j<=M;j++){
        char cc;cin >> cc;
        if(cc=='*') U=i,V=j;
        else c[i][j]=(cc=='X');
    }
    for(int t=0;t<=1;t++){
        for(int i=1;i<=N;i++) for(int j=1;j<=M-t;j++){
            int val=c[i][j]+c[i][j+t];
            up[t][i][j]=(val?i:up[t][i-1][j]);
        }
        for(int i=1;i<=N-t;i++) for(int j=1;j<=M;j++){
            int val=c[i][j]+c[i+t][j];
            lt[t][i][j]=(val?j:lt[t][i][j-1]);
        }
    }
    for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];

    queue<pii> q;
    q.push({X,Y});d[X][Y]=1;
    while(!q.empty()){
        auto [x,y]=q.front();q.pop();
        //cout << x << ' ' << y << '\n';
        for(int t=0;t<4;t++){
            int xt=x+dx[t],yt=y+dy[t];
            //cout << "nxt " << xt << ' ' << yt << '\n';
            if(out(xt,yt) || d[xt][yt]) continue;
            if(check(x,y,xt,yt)){
                cout << x << ' ' << y << ' ' << xt << ' ' << yt << '\n';
                d[xt][yt]=1,q.push({xt,yt});
            }
        }
    }
    cout << (d[U][V]?"YES":"NO") << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 8152kb

input:

32 16 23 15
3 8 4 1
................................
................................
................................
................................
................................
*...............................
................................
................................
...................

output:

9 5 9 4
9 5 9 6
9 5 8 5
9 5 10 5
9 4 9 3
9 4 8 4
9 4 10 4
9 6 9 7
9 6 8 6
9 6 10 6
8 5 7 5
10 5 11 5
9 3 9 2
9 3 8 3
9 3 10 3
8 4 7 4
10 4 11 4
9 7 9 8
9 7 8 7
9 7 10 7
8 6 7 6
10 6 11 6
7 5 6 5
11 5 12 5
9 2 9 1
9 2 8 2
9 2 10 2
8 3 7 3
10 3 11 3
7 4 6 4
11 4 12 4
9 8 9 9
9 8 8 8
9 8 10 8
8 7 7 7
1...

result:

wrong output format YES or NO expected, but 9 found

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #89:

score: 0
Wrong Answer
time: 0ms
memory: 8276kb

input:

105 31 8 4
70 27 75 26
.........................................................................................................
.........................................................................................................
....................................................................

output:

28 76 28 75
28 76 28 77
28 76 27 76
28 76 29 76
28 75 28 74
28 75 27 75
28 75 29 75
28 77 28 78
28 77 27 77
28 77 29 77
27 76 26 76
29 76 30 76
28 74 28 73
28 74 27 74
28 74 29 74
27 75 26 75
29 75 30 75
28 78 28 79
28 78 27 78
28 78 29 78
27 77 26 77
29 77 30 77
26 76 25 76
30 76 31 76
28 73 28 72
...

result:

wrong output format YES or NO expected, but 28 found

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%