QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #688805 | #7751. Palindrome Path | icpc_zhzx034 | TL | 995ms | 3996kb | C++14 | 2.8kb | 2024-10-30 13:40:15 | 2024-10-30 13:40:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define fi first
#define se second
#define mk make_pair
#define eb emplace_back
#define rep(i,l,r) for(int i=(l); i<=(r); ++i)
#define rep_(i,l,r) for(int i=(l); i>=(r); --i)
typedef long long lr;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
constexpr int mod1=998244353,mod2=1e9+7;
constexpr db pi=3.141592653589793,eps=1e-9;
constexpr int inf32=0x3f3f3f3f,Inf32=0xc0c0c0c0;
constexpr lr inf64=0x3f3f3f3f3f3f3f3f,Inf64=0xc0c0c0c0c0c0c0c0;
template<typename T>il T Max(T x,T y) { return (x>y)? x:y; }
template<typename T>il T Min(T x,T y) { return (x<y)? x:y; }
template<typename T>il T gcd(T x,T y) { return (!y)? x:gcd(y,x%y); }
template<typename T>il T Abs(T x) { return (x>0)? x:(-x); }
template<typename T>il T Rnd(T l,T r,mt19937_64 &eng)
{
uniform_int_distribution<T> uid(l,r);
return uid(eng);
}
mt19937_64 eng(chrono::high_resolution_clock::now().time_since_epoch().count());
constexpr int N=32;
int n,m,sx,sy,fx,fy;
int cnt,vis[N][N];
string s[N],t;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
il int val(int X,int Y)
{
if(X<1||X>n||Y<1||Y>m||!s[X][Y])
return 0;
return 1;
}
il void chk()
{
cnt=(sx==fx&&sy==fy)? 1:2;
rep(i,1,n)
rep(j,1,m)
{
vis[i][j]=0;
if(!s[i][j])
++cnt;
}
vis[sx][sy]=1,vis[fx][fy]=1,t="";
int nsx=sx,nsy=sy,nfx=fx,nfy=fy;
rep(p,1,90000)
{
if(cnt==n*m&&Abs(nsx-nfx)+Abs(nsy-nfy)<=1)
{
rep(i,0,p-2)
cout<<t[i];
if(nsx>nfx)
cout<<'U';
if(nsx<nfx)
cout<<'D';
if(nsy>nfy)
cout<<'L';
if(nsy<nfy)
cout<<'R';
rep_(i,p-2,0)
cout<<t[i];
cout<<'\n';
exit(0);
}
int flag=0;
rep(i,0,3)
flag|=(val(nfx-dx[i],nfy-dy[i])|(!val(nfx+dx[i],nfy+dy[i])));
if(!flag)
return;
int dir=eng()&3;
while(!(val(nfx-dx[dir],nfy-dy[dir])|(!val(nfx+dx[dir],nfy+dy[dir]))))
dir=eng()&3;
if(dir==0)
t+="L";
if(dir==1)
t+="R";
if(dir==2)
t+="U";
if(dir==3)
t+="D";
if(val(nsx+dx[dir],nsy+dy[dir]))
nsx+=dx[dir],nsy+=dy[dir];
int op=Rnd(val(nfx+dx[dir],nfy+dy[dir]),val(nfx-dx[dir],nfy-dy[dir]),eng);
if(op)
nfx-=dx[dir],nfy-=dy[dir];
if(!vis[nsx][nsy])
vis[nsx][nsy]=1,++cnt;
if(!vis[nfx][nfy])
vis[nfx][nfy]=1,++cnt;
}
}
il void Solve()
{
cin>>n>>m;
rep(i,1,n)
cin>>s[i],s[i]=" "+s[i];
cin>>sx>>sy>>fx>>fy;
rep(i,1,n)
rep(j,1,m)
s[i][j]^=48;
int Q=200;
rep(i,1,Q)
chk();
cout<<-1<<'\n';
return;
}
int main()
{
#ifdef LOCAL
string fpre="test",isuf="in",osuf="out";
assert(freopen((fpre+"."+isuf).c_str(),"r",stdin));
assert(freopen((fpre+"."+osuf).c_str(),"w",stdout));
#endif
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
while(T--)
Solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
input:
2 2 11 11 1 1 2 2
output:
DRLUDRLUDURUDULRDULRD
result:
ok Valid Solution (Length = 21).
Test #2:
score: 0
Accepted
time: 756ms
memory: 3996kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
RDLDLUUDDUUDLUULDURLDRLRRRLDRRLUDLDRDUDLDLULDUDRUULLDDDUUDULULRDLRRDDUUDLLRDLLLUDDDURDDDLUDLULRDLULRDDRULULUDRLURRRRRRLDDLDDUULDRULLDRLRLRLDLDRDUDLDRDDUUDUDUDLDRDLULULDRUUDURRUDUURDLULULDRDLDUDUDUUDDRDLDUDRDLDLRLRLRDLLURDLUUDDLDDLRRRRRRULRDULULURDDRLULDRLULDULDDDRUDDDULLLDRLLDUUDDRRLDRLULUDUUDDDLLUU...
result:
ok Valid Solution (Length = 348).
Test #5:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
DRLLRDDUUURRDDLRLDDULDUDDDLDUUDDLUDRRULDDUDDDDRLULDUDRRDRDRURDURUDRDRURRLDUUDRRLRDULRUUULLDDULURDULRLLLDRLUDLLLLURRLLRURRDUULRUDDUDRUULRRUDDULLUUDUDRLLURLLURDLDLDRULLRULLRDUDUULLUDDURRLUURDUDDURLUUDRRURLLRRULLLLDULRDLLLRLUDRULUDDLLUUURLUDRLRRDUUDLRRURDRDURUDRURDRDRRDUDLULRDDDDUDDLURRDULDDUUDLDDDUDLU...
result:
ok Valid Solution (Length = 319).
Test #6:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
5 3 111 100 111 001 111 4 3 3 2
output:
RDLLUURDDURULLDRULULDRDRULRUDRDURDRDLDRRRDUDLRDULRLDRRUDLUDDDLLRURLDLDDLRUDULDRLUDDDUDDRRUUULLUUULLUUURRDDUDDDULRDLUDURLDDLDLRURLLDDDULDURRDLRLUDRLDUDRRRDLDRDRUDRDURLURDRDLULURDLLURUDDRUULLDR
result:
ok Valid Solution (Length = 191).
Test #7:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
UDRUDRURLURLLRLULDLULLURLDUDUDDLLDRRLRLRLLRULLLRLRRUUDLLULURDURDRRRDDUUULDLDDLUDDRURULULRLLLRDLLDLLLRDDUDDLUDLLUDLUULDULRRRRRRLUDRLULRLUUULRDULRLDDDURUDUULRRUDDDLLRDLLDUDULRLUUURDLDDDUDUUDLLLDUDRURRLUDDURLUDLDLRDRLRLDURURLRDLULUDLRRLDUDDRUUDDLRUDRLRURURUUDDDDLLUDRLURLRRUUULUDLRRRRLRRRLUDULRLUULDUDDL...
result:
ok Valid Solution (Length = 753).
Test #8:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
5 3 101 111 100 111 100 4 1 2 2
output:
LRDDDULLRRRRRURUURRDLRUDURRRLRUURLLUULDDRRLULULRDDLRDLRLLLLRRRUDULURLRLLLLLULUDRRDULULLLLLRLRULUDURRRLLLLRLDRLDDRLULULRRDDLUULLRUURLRRRUDURLDRRUURURRRRRLLUDDDRL
result:
ok Valid Solution (Length = 160).
Test #9:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
5 5 01110 10110 11110 11011 11100 2 4 5 1
output:
LRDLLDLDLDUUUURURDRLUDUURRDRURRRUUURDDRURDRDUDLULUDDDRRDDULUUDURUDUDURRDUDURRDULLDDRLLLDDRRDRRLRLUDRLUULRRRRRUUULLRDDULRDUDLDRDDUDDULLLLULDLRLUDLRLLLRRLRUDUUDLRRLURLRUDLRULURRUDLLRRLRULURULRRLRLULRDULDLLRLLRUDLRRLRRUUULDDUURLRDRDLRUULDRLLUDDRRRLULLULLUURRLRRRLLLUULLRRLUULDDDLULDLLULDLLRRRRUUURRRLRLR...
result:
ok Valid Solution (Length = 841).
Test #10:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
5 3 011 111 110 111 011 3 1 2 1
output:
UUDDUULULUDRUULDLULLLRRUDRRRULDDDDLURRRDURRLLLULDLUURDULULUUDDUU
result:
ok Valid Solution (Length = 64).
Test #11:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
4 5 11111 11111 11111 11111 3 2 1 3
output:
URLLLUURLURUDRLLURLDRLRLDURRLDLDUUUDRRDDRLRLLUDRRDLRRUUUURRLDRRDULLRLRDDRRDUUUDLDLRRUDLRLRDLRULLRDURULRUULLLRU
result:
ok Valid Solution (Length = 110).
Test #12:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
5 5 11111 10101 11111 10101 11111 2 5 1 1
output:
LLULRULDURRRUUURRLRLRULDLUDLRLRLUDDDULRDLDDRDLLLRUDDDDLRDUDRDRRLRDLUULUDLDRLLUDLDDUDUUDRRDRLUDUURLRRLLDRRULRDDDLRRLLLRURDRLDRRDLRDRURLLLRRLDDDRLURRDLLRRLRUUDULRDRRDUUDUDDLDULLRDLDULUULDRLRRDRDUDRLDDDDURLLLDRDDLDRLUDDDULRLRLDULDLURLRLRRUUURRRUDLURLULL
result:
ok Valid Solution (Length = 250).
Test #13:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
4 5 11111 10000 11111 00001 1 3 4 5
output:
RRDRURLRRUDRDRUDDLRULULLLULURLDDURDRDURRLRURDRR
result:
ok Valid Solution (Length = 47).
Test #14:
score: 0
Accepted
time: 739ms
memory: 3752kb
input:
3 5 10100 00010 00111 1 3 1 1
output:
-1
result:
ok No Solution.
Test #15:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
4 5 10001 11111 11100 11111 4 5 3 1
output:
LUDDDLDDDRURULRLDLULUUDDDLUDLLURULUULUUDLRDLRLDUDLLLRULRLRULUULRDDDULUURUDRUDDRRLLRUUURLLRRDDURDURUULUDDDRLUULURLRLURLLLDUDLRLDRLDUULUULURULLDULDDDUULULDLRLURURDDDLDDDUL
result:
ok Valid Solution (Length = 169).
Test #16:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
3 5 11111 10100 11111 1 2 3 5
output:
DRLDRRRURDURURLULRRUDUURUUDUURRDRLUDDLURURLDUUURLDRUDDDUDDUDDDUURRUURRRLRDLLLDLRLLLULRLLDLUUUDDDRUDDURDULURRULUDRUDDURDDDUUULDLLRLULLLRLDLLLDRLRRRUURRUUDDDUDDUDDDURDLRUUUDLRURULDDULRDRRUUDUURUUDURRLULRURUDRURRRDLRD
result:
ok Valid Solution (Length = 214).
Test #17:
score: 0
Accepted
time: 930ms
memory: 3664kb
input:
4 5 01110 10101 11011 10111 1 3 2 3
output:
-1
result:
ok No Solution.
Test #18:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
5 5 11111 11111 11111 11111 11111 1 3 5 2
output:
LLRLRDRRDLLRDULUUDULDDLLDRLLLDDLLULDDDLLLLURULRRDLDDLRLRRLRRURRRDLULUULULDDDLULUULULDRRRURRLRRLRLDDLDRRLURULLLLDDDLULLDDLLLRDLLDDLUDUULUDRLLDRRDRLRLL
result:
ok Valid Solution (Length = 149).
Test #19:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
5 5 11111 10101 11111 10101 11111 5 1 2 3
output:
LRLLUDRRULRRRUDUUDDDRLULDDDLLLUURDRDRDDDULDRRUDRLDRRRLLLLRDULDLDDULDLLRDDURLDDDLRLLUDUDULDURLRUULRDLRRDLLRULLRRUUDRUDURRLURURLDDRDLUDLDDURRRULDDULLUULLUDDLURRRUDDLDULDRDDLRURULRRUDURDUURRLLURLLDRRLDRLUURLRUDLUDUDULLRLDDDLRUDDRLLDLUDDLDLUDRLLLLRRRDLRDURRDLUDDDRDRDRUULLLDDDLULRDDDUUDURRRLURRDULLRL
result:
ok Valid Solution (Length = 296).
Test #20:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5 5 11111 10000 11111 00001 11111 4 5 5 3
output:
DRDRLLULUULUULRRULRLRDUUULLLDRRDLRDLUDDDUUUDRLDDLUURLUULRRUDDUDUULLLURUUULRUUDLDLRURLLRDRDLDULDLRDDRUUURRRUDURUDRLUDUDLDDDDUULLDRUUDRUDLUULUDLLDDUULRRDURDDDUURDRURRDUURDDURDURULDUULUDUDRULUDLLRLDLUURUDLUUDDRRDLLDDLDDLLLRRRDRULRLDLRDULDRRLRUDDLRRRRRDLDULDDDDDDURRULDDLDLDRDULRDRDDLRUDLDDUDLLURLURRLURD...
result:
ok Valid Solution (Length = 1309).
Test #21:
score: 0
Accepted
time: 925ms
memory: 3756kb
input:
5 5 01010 10101 10101 11001 10011 4 1 5 4
output:
-1
result:
ok No Solution.
Test #22:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
5 5 10101 11111 10101 11111 11111 3 1 2 4
output:
LDLRLRUDLRURDLDLLRURULURLLLULLLLUUUUUDRRLURLURLLDDRRLDLDRLRRUURLDRRLLUUURRRRDLLRDURDLRURRLRDDDDDRLRRURLDRUDRLLDRRRRUUULLRRDLRUURRLRDLDLRRDDLLRULRULRRDUUUUULLLLULLLRULURURLLDLDRURLDURLRLDL
result:
ok Valid Solution (Length = 187).
Test #23:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
5 5 00001 11111 01110 01111 01111 1 5 5 2
output:
LRDLLDUDRDLUUDURDDDLLRUDRUUDDLURRLUULUUDULULUDDLLUDRDLULULLRULRDLURLRRDLLRRDLDRDDUURUDUUDDDLLLULUUULDUDRRDRLRLULUDUURLURDDRLRUULDLDUDLULDRURLRDRDRLRURDLULDUDLDLUURLRDDRULRUUDULULRLRDRRDUDLUUULULLLDDDUUDURUUDDRDLDRRLLDRRLRULDRLURLLULULDRDULLDDULULUDUULUULRRULDDUURDURLLDDDRUDUULDRDUDLLDRL
result:
ok Valid Solution (Length = 287).
Test #24:
score: 0
Accepted
time: 995ms
memory: 3832kb
input:
5 5 01011 10111 11011 10101 01110 4 1 2 3
output:
-1
result:
ok No Solution.
Test #25:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
10 8 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 7 7 3 6
output:
RUDRLDLULRUUDDDDRRUUUDLRDDRULDLULLLRURRLUURRRDRLLLLLUULDUUURRLULDURDDULDDRLURLURUURUUURUULURDULRRRULRDRRUULDDRURLURRDLLRLUDLURRLRLRDDUDUDRRRDLDRDDLRURRDUDDDLLRUUDLLDLDLRRLRRUDLRUULRLRRULRLRURLRLLULLLRRUDDRLLLUDULRRRRRDLUDDUDRULUDUUUUDLLDRDULULURDLUDLDLLLRLULRURUURLRUUULLRRUULUDDULDRDLLRLUULLDDDRDRUU...
result:
ok Valid Solution (Length = 1343).
Test #26:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
10 6 111111 101010 111111 101010 111111 101010 111111 101010 111111 101010 1 6 2 3
output:
RRLRLDULRRUDRULRLRDUUULDLRLUUDRULRLUDLLRDRRRLRLUURULRLRURUUUUDRLDRDLUDULUUULDLRRLLDRLLUDRRRDDURUDLLLRLDUDRLDRDLRRLDRDDDULLLRLUDRRUDLLDURDLRULUULRRRRDLDDRLDDRLUDDDURURDDDUUDDDRDDLRUDUDRDRUDLURULDUULDDUUDDRDUDUDUDRDUURRDDUUURRRDLDULRRDUUDULLDULDRRDRUDRULUDLDDLDDRLRLRRDURULLLLLDRRDURLRULULDRLUULRUDDUDR...
result:
ok Valid Solution (Length = 1465).
Test #27:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
10 10 1111111111 1000000000 1111111111 0000000001 1111111111 1000000000 1111111111 0000000001 1111111111 1000000000 5 5 5 2
output:
RLULLLDURDRRRULRLLLLRRLLLLURURLULLLRUDULRRRUDDLRULULULLUDULRRLUDLDULLLRUDDDRULURUULLLLDLDUDDRDURURULRUDLDLLDUDRRLLLRDDLDUDDDUDDDULRURURURLRDRLDLUDLRRRURDURUDDDDURDDRULRURLLRUUDLULULLRRRDUDLULRDDDLUDUDRRUDLRDRUUUDRRRRLUDURRLDRLDLDUULLRRRRDURDLRLURDLRULDUUDLUDDUURRDLDLRURDRUDULRDULULLDLRRLURDRRDURRUUR...
result:
ok Valid Solution (Length = 11109).
Test #28:
score: -100
Time Limit Exceeded
input:
10 10 1010110101 0000011010 1001001001 0011111000 1000111100 1011101001 1100110011 0110001011 0011111000 0101011101 7 5 4 3
output:
-1