QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #499508 | #6723. Grid with Arrows | Railgun2334 | WA | 42ms | 32524kb | C++20 | 7.0kb | 2024-07-31 15:03:48 | 2024-07-31 15:03:49 |
Judging History
answer
#include<bits/stdc++.h>
#define endl "\n"
#define int long long
#define x first
#define y second
#define MAXN 1005
#define pii pair<int,int>
using namespace std;
int n,m,p,x,y,T;
pii fa[MAXN][MAXN];
pii fa2[10005][15];
pii fa3[10005][15];
bool flag[1005][1005];
bool flag2[10005][15];
bool flag3[10005][15];
string s[100005];
int a[1005][1005];
int a2[10005][105];
int a3[10005][105];
pii fid(char str,int x,int y)
{
if(flag[x][y])
{
return fa[x][y];
}
flag[x][y]=true;
if(str=='r')
{
if(y+a[x][y]<=m)
{
return fa[x][y]=fid(s[x][y+a[x][y]],x,y+a[x][y]);
}
else
{
return {x,y};
}
}
else if(str=='d')
{
if(x+a[x][y]<=n)
{
return fa[x][y]=fid(s[x+a[x][y]][y],x+a[x][y],y);
}
else
{
return {x,y};
}
}
else if(str=='u')
{
if(x-a[x][y]>=1)
{
return fa[x][y]=fid(s[x-a[x][y]][y],x-a[x][y],y);
}
else
{
return {x,y};
}
}
else if(str=='l')
{
if(y-a[x][y]>=1)
{
return fa[x][y]=fid(s[x][y-a[x][y]],x,y-a[x][y]);
}
else
{
return {x,y};
}
}
return {x,y};
}
pii fid2(char str,int x,int y)
{
if(flag2[x][y])
{
return fa2[x][y];
}
flag2[x][y]=true;
if(str=='r')
{
if(y+a2[x][y]<=m)
{
return fa2[x][y]=fid(s[x][y+a2[x][y]],x,y+a2[x][y]);
}
else
{
return {x,y};
}
}
else if(str=='d')
{
if(x+a2[x][y]<=n)
{
return fa2[x][y]=fid(s[x+a2[x][y]][y],x+a2[x][y],y);
}
else
{
return {x,y};
}
}
else if(str=='u')
{
if(x-a[x][y]>=1)
{
return fa2[x][y]=fid(s[x-a2[x][y]][y],x-a2[x][y],y);
}
else
{
return {x,y};
}
}
else if(str=='l')
{
if(y-a[x][y]>=1)
{
return fa2[x][y]=fid(s[x][y-a2[x][y]],x,y-a2[x][y]);
}
else
{
return {x,y};
}
}
return {x,y};
}
pii fid3(char str,int x,int y)
{
if(flag3[y][x])
{
return fa3[y][x];
}
flag3[y][x]=true;
if(str=='r')
{
if(y+a3[y][x]<=m)
{
return fa3[y][x]=fid(s[x][y+a3[y][x]],x,y+a3[y][x]);
}
else
{
return {x,y};
}
}
else if(str=='d')
{
if(x+a3[y][x]<=n)
{
return fa3[y][x]=fid(s[x+a3[y][x]][y],x+a3[y][x],y);
}
else
{
return {x,y};
}
}
else if(str=='u')
{
if(x-a3[y][x]>=1)
{
return fa3[y][x]=fid(s[x-a3[y][x]][y],x-a3[y][x],y);
}
else
{
return {x,y};
}
}
else if(str=='l')
{
if(y-a3[y][x]>=1)
{
return fa3[y][x]=fid(s[x][y-a3[y][x]],x,y-a3[y][x]);
}
else
{
return {x,y};
}
}
return {x,y};
}
void solve()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
fid(s[i][j],i,j);
}
}
}
void solve2()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
fid2(s[i][j],i,j);
}
}
}
void solve3()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
fid3(s[i][j],i,j);
}
}
}
signed main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
cin>>T;
//init(n);
while(T--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i]=' '+s[i];
}
if(n<=1000&&m<=1000)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
fa[i][j]={i,j};
}
}
solve();
/*
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<fa[i][j].x<<" "<<fa[i][j].y<<endl;
}
}*/
pii ans=fa[1][1];
bool f=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(ans!=fa[i][j])
{
f=1;
break;
}
}
if(f==1)
break;
}
if(f==1)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
else if(n<=10000&&m<=100)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a2[i][j];
fa2[i][j]={i,j};
}
}
solve2();
/*
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<fa[i][j].x<<" "<<fa[i][j].y<<endl;
}
}*/
pii ans=fa2[1][1];
bool f=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(ans!=fa2[i][j])
{
f=1;
break;
}
}
if(f==1)
break;
}
if(f==1)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
else if(n<=100&&m<=10000)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a3[j][i];
fa3[j][i]={i,j};
}
}
solve3();
/*
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<fa[i][j].x<<" "<<fa[i][j].y<<endl;
}
}*/
pii ans=fa3[1][1];
bool f=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(ans!=fa3[j][i])
{
f=1;
break;
}
}
if(f==1)
break;
}
if(f==1)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11884kb
input:
2 2 3 rdd url 2 1 1 1 1 2 2 2 rr rr 1 1 1 1
output:
Yes No
result:
ok 2 token(s): yes count is 1, no count is 1
Test #2:
score: -100
Wrong Answer
time: 42ms
memory: 32524kb
input:
1109 5 8 rddddldl drruludl rrldrurd urrrlluu uurrulrl 4 4 1 2 4 3 1 6 1 3 5 1 1 1 3 6 2 4 1 1 2 1 1 1 2 3 4 2 4 3 3 3 4 1 1 2 2 5 1 5 7 9 rdrddrdll urrdruldl ruullrulu drrlrlddl rrrdddlll ruulururl ruurrlluu 7 1 1 1 2 1 2 3 6 1 7 3 1 3 1 2 1 8 2 2 1 2 4 3 1 2 2 2 2 4 1 1 5 3 3 1 3 4 6 1 2 1 2 7 7 6 ...
output:
Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No Yes ...
result:
wrong answer expected YES, found NO [5th token]