QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#532846#9164. ToyDimash#0 5ms21628kbC++233.0kb2024-08-25 13:16:232024-08-25 13:16:23

Judging History

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

  • [2024-08-25 13:16:23]
  • 评测
  • 测评结果:0
  • 用时:5ms
  • 内存:21628kb
  • [2024-08-25 13:16:23]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 2e3 + 12, MOD = (int)1e9 + 7;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int n, m, k, l, x, y;
int a[N][N],ph[N][N],nh[N][N],pv[N][N],nv[N][N];
bool vis[N][N];
bool ok(int X,int Y) {
    return (min(X,Y) >= 1 && X <= n && Y <= m && !a[X][Y]);
}
int inter(int l,int r,int l1,int r1) {
    // cout << l << ' ' << r << ' ' << l1 << ' ' << r1 << '\n';
    return max(0,min(r,r1) - max(l,l1) + 1);
}
void test(){
    cin >> n >> m >> k >> l;
    swap(n,m);
    int x1, y1;
    cin >> y >> x >> y1 >> x1;
    y = y1;
    x++;
    y++;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char t;
            cin >> t;
            if(t == 'X') {
                a[i][j] = 1;
            }
            if(t == '*') {
                x1 = i;
                y1 = j;
            }
            if(a[i][j]) {
                ph[i][j] = j;
            } else {
                ph[i][j] = ph[i][j - 1];
            }
        }
        nh[i][m + 1] = m + 1;
        for(int j = m;j >= 1;j--) {
            if(a[i][j]) {
                nh[i][j] = j;
            } else {
                nh[i][j] = nh[i][j + 1];
            }
        }
    }
    for(int i = 1;i <= m;i++) {
        for(int j = 1; j <= n; j++) {
            if(a[j][i]) {
                pv[j][i] = j;
            } else {
                pv[j][i] = pv[j - 1][i];
            }
            // cout << j << ' ' << i << ' ' << pv[j][i] << '\n';   
        }
        nv[n + 1][i] = n + 1;
        for(int j = n; j >= 1; j--) {
            if(a[j][i]) {
                nv[j][i] = j;
            } else {
                nv[j][i] = nv[j + 1][i];
            }
        }
    }
    queue<pair<int,int>> q;
    q.push({x,y});
    vis[x][y] = 1;
    while(!q.empty()) {
        auto [x_,y_] = q.front();
        // cout << x_ << ' ' << y_ << '\n';
        if(x_ == x1 && y_ == y1) {
            cout << "Yes\n";
            return;
        }
        q.pop();
        for(int i = 0; i < 4; i++) {
            int _x = x_ + dx[i],_y = y_ + dy[i];
            if(!ok(_x,_y) || vis[_x][_y]) continue;
            // cout << _x << ' ' << _y << '\n';
            if(x != _x) {
                if(inter(ph[x_][y_] + 1,nh[x_][y_] - 1,ph[_x][_y] + 1,nh[_x][_y] - 1) >= k) {
                    vis[_x][_y] = 1;
                    q.push({_x,_y});
                }
            } else {
                // cout << inter(pv[x_][y_] + 1,nv[x_][y_] - 1,pv[_x][_y] + 1,nv[_x][_y] - 1) << ' ' << "x\n";
                if(inter(pv[x_][y_] + 1,nv[x_][y_] - 1,pv[_x][_y] + 1,nv[_x][_y] - 1) >= l) {
                    vis[_x][_y] = 1;
                    q.push({_x,_y});
                }
            }
        }
    }
    cout << "No\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 14
Accepted
time: 1ms
memory: 7876kb

input:

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

output:

Yes

result:

ok answer is YES

Test #2:

score: 14
Accepted
time: 0ms
memory: 10224kb

input:

50 50 22 14
26 34 36 33
..................................................
..................................................
..................................................
..................................................
..................................................
........................

output:

Yes

result:

ok answer is YES

Test #3:

score: 14
Accepted
time: 1ms
memory: 8100kb

input:

50 50 50 50
0 18 2 0
..................................................
...............................................X..
..................................................
..................................................
..................................................
...........................

output:

No

result:

ok answer is NO

Test #4:

score: 14
Accepted
time: 0ms
memory: 10008kb

input:

5 47 4 47
1 25 3 0
.X...
.....
.....
.X...
.....
.....
.....
.....
.....
.....
.....
.....
..*..
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
X....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....

output:

Yes

result:

ok answer is YES

Test #5:

score: 14
Accepted
time: 1ms
memory: 8248kb

input:

50 50 29 46
11 5 29 3
..................................................
..................................................
..................................................
..................................................
....................X.......................X.....
..........................

output:

No

result:

ok answer is NO

Test #6:

score: 14
Accepted
time: 0ms
memory: 10280kb

input:

50 50 50 50
0 37 22 0
............X.............X..............X........
..................................................
..................................................
....................................X.............
................................X.................
....................X.....

output:

No

result:

ok answer is NO

Test #7:

score: 14
Accepted
time: 1ms
memory: 8064kb

input:

27 34 19 18
5 29 20 14
............X..X.X.X..XX..X
.....X..X...XX.............
.......X.X........X........
X...................X...X..
....XX.....................
.................X........X
..........X.X.....X.......X
..........X......X....X....
X..X........XX.....X.......
..X.X............X..........

output:

No

result:

ok answer is NO

Test #8:

score: 14
Accepted
time: 0ms
memory: 8300kb

input:

50 50 16 16
21 35 36 33
.X.............XX....X...X.......X................
.................X.......X.........X........X.....
...X........X......XX........X.......X...........X
.X......X.......X.....X.X................X.XX....X
......X.........................X.............X.X.
........X...X..X...X....

output:

No

result:

ok answer is NO

Test #9:

score: 14
Accepted
time: 2ms
memory: 10320kb

input:

50 50 50 50
0 20 3 0
.......X..........................................
....X............X.......X.......X...........X....
.......X....X........X..X.......X..........X..X...
.X......X.......X.................X.............X.
.................X.X....X..XX.....................
.......X...................

output:

No

result:

ok answer is NO

Test #10:

score: 14
Accepted
time: 1ms
memory: 8048kb

input:

4 7 4 5
0 2 0 1
.X..
.X..
....
..X.
..X.
.XX*
XXXX

output:

No

result:

ok answer is NO

Test #11:

score: 14
Accepted
time: 0ms
memory: 10236kb

input:

50 50 13 13
2 46 11 36
.X.X.X.....XX.XX.X..XX..XXXXXXX.XXX...XX.X.X.XXXX.
.X..X...X.X.X.X.X.X..XX..XX.XXXX..X.X..XXX...X..X.
X..X...X....XX....XX......X...X..XXX.X.X..X.X.....
...X.XX...X..XX.X..XX.X...X.X...X.XXX.XX..XX..XX..
..X.XX...X.X.X..X.X.......X.X......X..X..X...X.X.X
......XX......X..X..X....

output:

No

result:

ok answer is NO

Test #12:

score: 14
Accepted
time: 0ms
memory: 15860kb

input:

50 50 50 50
0 46 6 0
XX.....X....X...X.X.X..XX..XX...X.XX..X.......X...
XXX........X.X.X.XX..X..XX..XXX....X.XX.....X...XX
..X.X...X.X.........X..X....XX....X*XXXXXXX...XX..
....X..XX....X.X.X..X..XXX...XXX..XXX.X..X.XX.XXXX
XXX......X.X.....X.X.........XXXXX.XX..X.X.X.XXX.X
.X.....XXXX....X...X.XXX...

output:

No

result:

ok answer is NO

Test #13:

score: 0
Wrong Answer
time: 2ms
memory: 10460kb

input:

48 50 24 21
3 9 6 3
................................................
................................................
................................................
................................................
................................................
......................................

output:

Yes

result:

wrong answer expected NO, found YES

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #89:

score: 9
Accepted
time: 0ms
memory: 7964kb

input:

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

output:

Yes

result:

ok answer is YES

Test #90:

score: 9
Accepted
time: 0ms
memory: 16556kb

input:

300 300 4 8
231 246 234 240
...................................................................................................................................................................................................................................................................................

output:

Yes

result:

ok answer is YES

Test #91:

score: 9
Accepted
time: 5ms
memory: 16284kb

input:

300 300 10 10
151 143 155 137
.................................................................................................................................................................................................................................................................................

output:

Yes

result:

ok answer is YES

Test #92:

score: 9
Accepted
time: 0ms
memory: 8676kb

input:

159 68 6 2
95 54 98 54
.........................................................................X.....................................................................................
..........................X..................................................X..........................................

output:

Yes

result:

ok answer is YES

Test #93:

score: 9
Accepted
time: 4ms
memory: 18452kb

input:

300 300 10 10
11 147 12 143
.....................................................................X.................X.......................................*X..............................................X...................................................................................................

output:

Yes

result:

ok answer is YES

Test #94:

score: 9
Accepted
time: 0ms
memory: 18084kb

input:

300 300 10 10
289 237 298 236
.........................................................................................X.......................................................................................................................................................................................

output:

Yes

result:

ok answer is YES

Test #95:

score: 9
Accepted
time: 0ms
memory: 11132kb

input:

277 111 6 9
109 9 112 5
...................X..XX...........X.......X..................X...X.......X........X......X...........X....................X.......................X..X..X.........XX...................X..............X..........X..................X................X...................X............

output:

No

result:

ok answer is NO

Test #96:

score: 0
Wrong Answer
time: 4ms
memory: 21628kb

input:

300 300 6 6
126 5 131 1
.......X............XX..............X...X....XX..........X..X........X.X...X...........X.................X...............X..............X.....XX.............X....................................XX....X................X........X...................X.....X..........................

output:

Yes

result:

wrong answer expected NO, found YES

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%