QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#648447 | #7751. Palindrome Path | WrongAnswer_90 | WA | 0ms | 32612kb | C++23 | 6.9kb | 2024-10-17 19:01:48 | 2024-10-17 19:01:49 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vp vector<pii>
#define vt vector<tup>
#define all(x) x.begin(),x.end()
#define mp make_pair
#define FastI
#define FastO
#define int ll
bool ST;
static const ll MOD=998244353,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,Inf=4294967296,INF=4557430888798830399;
static const ld eps=1e-9,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
char out[1<<20],*p3=out;
using namespace std;
struct tup
{
int x,y,z;
tup(int X=0,int Y=0,int Z=0)
{x=X,y=Y,z=Z;}
};
#ifdef FastI
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
#ifdef FastO
#define putchar(x) (p3-out==1<<20?fwrite(out,1,1<<20,stdout),p3=out,0:0,*p3++=x)
#define puts(x) write(x,'\n')
#endif
namespace FastIO
{
template<typename T> inline void write(T x,char ch=' ')
{
if(is_same<char,T>::value)putchar(x);
else
{
if(x<0)x=-x,putchar('-');
static char st[25];
int top=0;
do st[top++]=x%10+'0',x/=10;while(x);
while(top)putchar(st[--top]);
}
ch!='~'?putchar(ch):0;
}
inline void write(const char*x,char ch=' ')
{
for(int i=0;x[i]!='\0';++i)putchar(x[i]);
ch!='~'?putchar(ch):0;
}
inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
inline void read(char s[])
{
int len=0;char st;
do st=getchar();while(st=='\n'||st==' ');
s[++len]=st,st=getchar();
while(st!='\n'&&st!=' '&&st!='\r')s[++len]=st,st=getchar();
s[++len]='\0';
}
template<typename T> inline void read(T &s)
{
char ch=getchar();s=0;
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
bool tf=(ch=='-'&&(ch=getchar()));
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
s=tf?-s:s;
}
inline void edl(){putchar('\n');}
template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
#ifdef FastO
struct Writer{~Writer(){fwrite(out,1,p3-out,stdout);}}Writ;
#endif
}
using namespace FastIO;
namespace MTool
{
inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
inline int sqr(int a){return 1ll*a*a%MOD;}
inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
inline int Cmod(int x){return (x%MOD+MOD)%MOD;}
inline void Mmod(int&x){x=(x%MOD+MOD)%MOD;}
template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int f[40][40][40][40];
queue<pair<pii,pii>> q;
int n,m;
char s[40][40];
char mv[4];
int sx,sy,ex,ey;
pair<pii,pii> from[40][40][40][40];
int val[40][40][40][40];
vi ans;
void print(int x1,int y1,int x2,int y2)
{
if(x1==sx&&y1==sy&&x2==ex&&y2==ey)return;
pair<pii,pii> p=from[x1][y1][x2][y2];
print(p.fi.fi,p.fi.se,p.se.fi,p.se.se);
ans.eb(val[x1][y1][x2][y2]);
}
inline void mian()
{
mv[0]='D',mv[1]='R',mv[2]='U',mv[3]='L';
read(n,m);
for(int i=1;i<=n;++i)read(s[i]);
read(sx,sy,ex,ey);
memset(f,127,sizeof(f));
f[sx][sy][ex][ey]=0;
q.e(mp(mp(sx,sy),mp(ex,ey)));
while(!q.empty())
{
pii x=q.front().fi,y=q.front().se;q.pop();
// cerr<<x.fi<<" "<<x.se<<" "<<y.fi<<" "<<y.se<<endl;
if(abs(x.fi-y.fi)+abs(x.se-y.se)==0)
{
print(x.fi,x.se,y.fi,y.se);
for(auto p:ans)putchar(mv[p]);
reverse(ans.begin(),ans.end());
for(auto p:ans)putchar(mv[p^2]);
return;
}
if(abs(x.fi-y.fi)+abs(x.se-y.se)==1)
{
print(x.fi,x.se,y.fi,y.se);
for(auto p:ans)putchar(mv[p]);
if(x.fi==y.fi+1)putchar('U');
else if(x.fi==y.fi-1)putchar('D');
else if(x.se==y.se-1)putchar('R');
else putchar('L');
reverse(ans.begin(),ans.end());
for(auto p:ans)putchar(mv[p]);
return;
}
for(int i=0;i<4;++i)
{
pii xx=mp(x.fi+dx[i],x.se+dy[i]);
if(xx.fi<=0||xx.fi>n||xx.se<=0||xx.se>m||s[xx.fi][xx.se]=='0')
xx=x;
pii yy=mp(y.fi+dx[i^2],y.se+dy[i^2]);
pii y2=mp(y.fi+dx[i],y.se+dy[i]);
// cerr<<i<<endl;
// cerr<<xx.fi<<" "<<xx.se<<endl;
// cerr<<yy.fi<<" "<<yy.se<<endl;
// cerr<<y2.fi<<" "<<y2.se<<endl;
if(yy.fi>0&&yy.fi<=n&&yy.se>0&&yy.se<=m&&s[yy.fi][yy.se]=='1')
{
if(Mmin(f[xx.fi][xx.se][yy.fi][yy.se],f[x.fi][x.se][y.fi][y.se]+1))
{
from[xx.fi][xx.se][yy.fi][yy.se]=mp(x,y);
val[xx.fi][xx.se][yy.fi][yy.se]=i;
q.e(mp(xx,yy));
// cerr<<"TO:"<<xx.fi<<" "<<xx.se<<" "<<yy.fi<<" "<<yy.se<<endl;
}
}
if(y2.fi<=0||y2.fi>n||y2.se<=0||y2.se>m||s[y2.fi][y2.se]=='0')
{
yy=y;
if(Mmin(f[xx.fi][xx.se][yy.fi][yy.se],f[x.fi][x.se][y.fi][y.se]+1))
{
from[xx.fi][xx.se][yy.fi][yy.se]=mp(x,y);
val[xx.fi][xx.se][yy.fi][yy.se]=i;
q.e(mp(xx,yy));
// cerr<<"TO:"<<xx.fi<<" "<<xx.se<<" "<<yy.fi<<" "<<yy.se<<endl;
}
}
}
// cerr<<endl;
// exit(0);
}
puts("-1");
}
inline void Mian()
{
int T=1;
// read(T);
while(T--)mian();
}
}
bool ED;
signed main()
{
// ios::sync_with_stdio(0);
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
double st=clock();
WrongAnswer_90::Mian();
double ed=clock();
cerr<<endl;
cerr<<"Time: "<<ed-st<<" ms\n";
cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 32612kb
input:
2 2 11 11 1 1 2 2
output:
DRD
result:
wrong answer (1,2) Not Visited