QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#498374 | #9164. Toy | bachbeo2007 | 0 | 8ms | 22380kb | C++23 | 2.2kb | 2024-07-30 13:07:45 | 2024-07-30 13:07:45 |
Judging History
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(x+1==u){
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;
if(query(x,p,x,p+K-1)) return false;
}
else if(y+1==v){
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;
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)) 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: 14
Accepted
time: 1ms
memory: 8116kb
input:
32 16 23 15 3 8 4 1 ................................ ................................ ................................ ................................ ................................ *............................... ................................ ................................ ...................
output:
YES
result:
ok answer is YES
Test #2:
score: 14
Accepted
time: 0ms
memory: 10508kb
input:
50 50 22 14 26 34 36 33 .................................................. .................................................. .................................................. .................................................. .................................................. ........................
output:
YES
result:
ok answer is YES
Test #3:
score: 14
Accepted
time: 1ms
memory: 8760kb
input:
50 50 50 50 0 18 2 0 .................................................. ...............................................X.. .................................................. .................................................. .................................................. ...........................
output:
NO
result:
ok answer is NO
Test #4:
score: 14
Accepted
time: 1ms
memory: 12428kb
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: 0ms
memory: 10576kb
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: 8544kb
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: 0ms
memory: 8268kb
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: 12416kb
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: 10404kb
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: 0ms
memory: 9848kb
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: 2ms
memory: 12352kb
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: 2ms
memory: 14272kb
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: 14
Accepted
time: 0ms
memory: 8460kb
input:
48 50 24 21 3 9 6 3 ................................................ ................................................ ................................................ ................................................ ................................................ ......................................
output:
NO
result:
ok answer is NO
Test #14:
score: 14
Accepted
time: 0ms
memory: 8624kb
input:
50 45 23 25 0 27 14 12 .................................................. .................................................. .................................................. .................................................. .................................................. .........................
output:
NO
result:
ok answer is NO
Test #15:
score: 14
Accepted
time: 0ms
memory: 8452kb
input:
50 46 23 25 2 25 20 16 .................................................. .................................................. .................................................. .................................................. .................................................. .........................
output:
NO
result:
ok answer is NO
Test #16:
score: 14
Accepted
time: 1ms
memory: 10792kb
input:
50 50 25 25 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ............................
output:
NO
result:
ok answer is NO
Test #17:
score: 14
Accepted
time: 1ms
memory: 10668kb
input:
50 50 24 24 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ............................
output:
NO
result:
ok answer is NO
Test #18:
score: 14
Accepted
time: 0ms
memory: 8544kb
input:
50 50 23 23 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ............................
output:
NO
result:
ok answer is NO
Test #19:
score: 14
Accepted
time: 0ms
memory: 10680kb
input:
50 50 25 25 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ............................
output:
YES
result:
ok answer is YES
Test #20:
score: 14
Accepted
time: 0ms
memory: 10380kb
input:
50 50 24 24 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ............................
output:
YES
result:
ok answer is YES
Test #21:
score: 14
Accepted
time: 1ms
memory: 10564kb
input:
50 50 23 23 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ............................
output:
YES
result:
ok answer is YES
Test #22:
score: 14
Accepted
time: 0ms
memory: 8472kb
input:
50 50 12 12 0 0 0 0 .........................X.......................* .........................X........................ .........................X........................ .........................X........................ .........................X........................ ............................
output:
YES
result:
ok answer is YES
Test #23:
score: 14
Accepted
time: 0ms
memory: 8712kb
input:
50 50 11 11 0 0 0 0 .........................X.......................* .........................X........................ .........................X........................ .........................X........................ .........................X........................ ............................
output:
YES
result:
ok answer is YES
Test #24:
score: 14
Accepted
time: 1ms
memory: 10512kb
input:
50 50 12 12 0 0 0 0 .........................X.......................* .........................X........................ .........................X........................ .........................X........................ .........................X........................ ............................
output:
YES
result:
ok answer is YES
Test #25:
score: 14
Accepted
time: 1ms
memory: 8520kb
input:
50 50 11 11 0 0 0 0 .........................X.......................* .........................X........................ .........................X........................ .........................X........................ .........................X........................ ............................
output:
YES
result:
ok answer is YES
Test #26:
score: 14
Accepted
time: 1ms
memory: 8544kb
input:
50 50 10 10 0 0 0 0 .........................X.......................* .........................X........................ .........................X........................ .........................X........................ .........................X........................ ............................
output:
YES
result:
ok answer is YES
Test #27:
score: 14
Accepted
time: 1ms
memory: 10512kb
input:
50 50 9 9 0 0 0 0 .........................X.......................* .........................X........................ .........................X........................ .........................X........................ .........................X........................ .........................X....
output:
YES
result:
ok answer is YES
Test #28:
score: 14
Accepted
time: 1ms
memory: 8424kb
input:
50 47 8 8 0 0 0 0 .................................................. .................................................. .................................................. .................................................. .................................................. ..............................
output:
YES
result:
ok answer is YES
Test #29:
score: 0
Wrong Answer
time: 1ms
memory: 8420kb
input:
45 48 10 10 0 0 0 0 ............................................. ............................................. ............................................. ............................................. ............................................. ............................................. .......
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: 1ms
memory: 10460kb
input:
105 31 8 4 70 27 75 26 ......................................................................................................... ......................................................................................................... ....................................................................
output:
YES
result:
ok answer is YES
Test #90:
score: 9
Accepted
time: 4ms
memory: 18524kb
input:
300 300 4 8 231 246 234 240 ...................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #91:
score: 9
Accepted
time: 3ms
memory: 18032kb
input:
300 300 10 10 151 143 155 137 .................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #92:
score: 9
Accepted
time: 2ms
memory: 10944kb
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: 3ms
memory: 19724kb
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: 4ms
memory: 19632kb
input:
300 300 10 10 289 237 298 236 .........................................................................................X.......................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #95:
score: 9
Accepted
time: 2ms
memory: 13480kb
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: 9
Accepted
time: 0ms
memory: 16436kb
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:
NO
result:
ok answer is NO
Test #97:
score: 9
Accepted
time: 0ms
memory: 17552kb
input:
300 300 10 10 30 92 34 92 ...X..........X.........................X....................XX........XX......X..X.......X..................X..X...X..X.........X..................X.........X...........................XX................X....XX.......................X...........X..............................
output:
NO
result:
ok answer is NO
Test #98:
score: 9
Accepted
time: 3ms
memory: 17020kb
input:
121 248 8 4 20 157 23 156 ...XXX.....XX..XXXX...XX.XXX....X..XXX....XX.XX..X..XX.X...X...X.X............X....X...XXX..XX..X..X....X.X..X..X.....XXX ...XX..XX.XX..XX..XX..X...X..X..X.......X.X..X.XX......X....XX.X..X..X.X.X...X..XXX.XXXX...XXXX..X..X...X.XX........X.X.X XXXXX....X.X.X..XXXX.XX..XX.XX...
output:
NO
result:
ok answer is NO
Test #99:
score: 9
Accepted
time: 5ms
memory: 21472kb
input:
300 300 9 5 55 124 55 121 XX.X...X..X.X..X.....X..X..X.X.X...XX.XXX...XXX........XXX.........X..XX..X.X......X....XXXXX.X.X.X.X......X..X.X...XXXX..X....X.XXXX....XX..XX.X......XX.XX..X.....X.X.X.XXXX.X.XX.XXX....XX.X..X.X.XX.X.X...XX.X.X.XX...X.....X..XXX..X.XX...XXX...X.XXX...XX..X....XX.XXX.X.XXX...
output:
NO
result:
ok answer is NO
Test #100:
score: 9
Accepted
time: 0ms
memory: 22380kb
input:
300 300 10 10 94 163 96 156 X..X.....X..XXX.X.XXXXX..XXX..X....X..XX..XXX...XXX....X.XXXXX...XX...XX.X...XX.X...XX..XX...X.X...X.X.XX...XX..X..X.....X.X........X.XXX...XXX.XX....X.X.X....X......XXX.XX.XX..XXXX...XX....X.X.X.X...XXX.......XX..X..XX.....X...XX..X...XX.....XXX.XXXXX..X.X...X...X.XX..X....
output:
NO
result:
ok answer is NO
Test #101:
score: 9
Accepted
time: 0ms
memory: 17696kb
input:
286 296 9 9 19 286 26 279 .....................................................................................................................................................................................................................................................................................
output:
NO
result:
ok answer is NO
Test #102:
score: 9
Accepted
time: 6ms
memory: 18160kb
input:
284 284 9 9 36 50 40 42 .......................................................................................................................................................................................................................................................................................
output:
NO
result:
ok answer is NO
Test #103:
score: 9
Accepted
time: 0ms
memory: 19008kb
input:
270 299 10 9 35 258 39 253 .............................................................................................................................................................................................................................................................................. .....
output:
NO
result:
ok answer is NO
Test #104:
score: 9
Accepted
time: 0ms
memory: 21072kb
input:
300 300 10 10 0 0 0 0 .........................................................................................................................................................................................................................................................................................
output:
NO
result:
ok answer is NO
Test #105:
score: 9
Accepted
time: 7ms
memory: 18676kb
input:
300 300 9 9 0 0 0 0 ...........................................................................................................................................................................................................................................................................................
output:
NO
result:
ok answer is NO
Test #106:
score: 9
Accepted
time: 4ms
memory: 19492kb
input:
300 300 8 8 0 0 0 0 ...........................................................................................................................................................................................................................................................................................
output:
NO
result:
ok answer is NO
Test #107:
score: 9
Accepted
time: 7ms
memory: 20448kb
input:
300 300 10 10 0 0 0 0 .........................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #108:
score: 9
Accepted
time: 7ms
memory: 20316kb
input:
300 300 9 9 0 0 0 0 ...........................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #109:
score: 9
Accepted
time: 3ms
memory: 17312kb
input:
300 300 8 8 0 0 0 0 ...........................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #110:
score: 9
Accepted
time: 7ms
memory: 18588kb
input:
300 300 10 10 0 0 0 0 ......................................................................................................................................................X..................................................................................................................................
output:
YES
result:
ok answer is YES
Test #111:
score: 9
Accepted
time: 8ms
memory: 19864kb
input:
300 300 9 9 0 0 0 0 ......................................................................................................................................................X....................................................................................................................................
output:
YES
result:
ok answer is YES
Test #112:
score: 9
Accepted
time: 8ms
memory: 17940kb
input:
300 300 10 10 0 0 0 0 ......................................................................................................................................................X..................................................................................................................................
output:
YES
result:
ok answer is YES
Test #113:
score: 9
Accepted
time: 0ms
memory: 18220kb
input:
300 300 9 9 0 0 0 0 ......................................................................................................................................................X....................................................................................................................................
output:
YES
result:
ok answer is YES
Test #114:
score: 9
Accepted
time: 7ms
memory: 18772kb
input:
300 300 8 8 0 0 0 0 ......................................................................................................................................................X....................................................................................................................................
output:
YES
result:
ok answer is YES
Test #115:
score: 9
Accepted
time: 3ms
memory: 17356kb
input:
300 300 7 7 0 0 0 0 ......................................................................................................................................................X....................................................................................................................................
output:
YES
result:
ok answer is YES
Test #116:
score: 9
Accepted
time: 4ms
memory: 19648kb
input:
300 289 8 8 0 0 0 0 ...........................................................................................................................................................................................................................................................................................
output:
YES
result:
ok answer is YES
Test #117:
score: 0
Wrong Answer
time: 8ms
memory: 21608kb
input:
285 293 5 5 0 0 0 0 ...........................................................................................................................................................................................................................................................................................
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%