QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#498395 | #9164. Toy | bachbeo2007 | 0 | 1ms | 8276kb | C++23 | 2.3kb | 2024-07-30 13:34:46 | 2024-07-30 13:34:47 |
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%