QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#532846 | #9164. Toy | Dimash# | 0 | 5ms | 21628kb | C++23 | 3.0kb | 2024-08-25 13:16:23 | 2024-08-25 13:16:23 |
Judging History
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%