QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351799 | #6422. Evil Coordinate | PorNPtree# | WA | 4ms | 3736kb | C++20 | 2.2kb | 2024-03-12 15:03:17 | 2024-03-12 15:03:18 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e5+5,dx[]={0,-1,1,0},dy[]={1,0,0,-1};const char To[]={'U','L','R','D'};
int T,c[7],cc[7],mx,my,x,y;string C,ans,ans1;
inline int to(char x)
{
if(x=='U') return 0;if(x=='D') return 3;
if(x=='L') return 1;if(x=='R') return 2;
}
inline void sol()
{
basic_string<int>g;g.clear();
for(int i=0;i<4;i++) if(c[i]) g+=i;x=0,y=0;
if(!g.size()) return cout<<ans<<"\n",void();
if(g.size()==1)
{
int t=g[0];bool ok=1;
for(int i=1;i<=c[t];i++)
{
x+=dx[t],y+=dy[t];
if(x==mx&&y==my){ok=0;break;}
}
if(ok)
{
for(int i=1;i<=c[t];i++) ans+=To[t];
cout<<ans<<"\n";return;
}int t1=t;
g.clear();
for(int i=0;i<4;i++) if(i!=t&&i!=3-t) g+=i;
ok=1;
for(int i:g) if(!cc[i]){ok=0;break;}
if(!ok) return cout<<"Impossible\n",void();
ans1+=To[g[0]];
for(int i=1;i<=c[t];i++) ans1+=To[t1];
ans1+=To[g[1]];bool O[4];memset(O,0,sizeof(O));
for(char i:ans)
{
int too=to(i);
if(!O[too])
{
O[too]=1;
if(too!=g[0]&&too!=g[1]) cout<<i;
}
else cout<<i;
}cout<<ans1<<"\n";return;
}
bool ok=1;int t=g[0];
for(int i=1;i<=c[t];i++)
{
x+=dx[t],y+=dy[t];
if(x==mx&&y==my){ok=0;break;}
}
if(!ok) swap(g[0],g[1]);t=g[0];
for(int i=1;i<=c[t];i++) ans+=To[t];t=g[1];
for(int i=1;i<=c[t];i++) ans+=To[t];cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;
while(T--)
{
memset(c,0,sizeof(c));cin>>mx>>my>>C;
if(!mx&&!my){cout<<"Impossible\n";continue;}
for(char x:C) c[to(x)]++;x=0,y=0;memcpy(cc,c,sizeof(c));
for(int i=0;i<4;i++) x+=dx[i]*c[i],y+=dy[i]*c[i];
if(x==mx&&y==my){cout<<"Impossible\n";continue;}ans=ans1="";
int mn=min(c[0],c[3]),X=0,Y=3;
if(dx[X]==mx&&dy[X]==my) swap(X,Y);
for(int i=1;i<=mn;i++) ans+=To[X],ans+=To[Y];
c[0]-=mn,c[3]-=mn;
mn=min(c[1],c[2]);X=1,Y=2;
if(dx[X]==mx&&dy[X]==my) swap(X,Y);
for(int i=1;i<=mn;i++) ans+=To[X],ans+=To[Y];
c[1]-=mn,c[2]-=mn;
sol();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3472kb
input:
5 1 1 RURULLD 0 5 UUU 0 3 UUU 0 2 UUU 0 0 UUU
output:
UDLRLRU UUU Impossible Impossible Impossible
result:
ok 5 cases
Test #2:
score: -100
Wrong Answer
time: 4ms
memory: 3736kb
input:
11109 6 0 RUDUDR 2 0 URU 0 0 UDRU 0 0 R -1 1 LDUUDDRUUL -1 5 RRUUUDUUU -8 4 RRDRLDR 2 0 UD 0 0 UUDD 3 -2 LDDLLLRR 3 -2 LDRURLDD 1 0 RRL -1 0 DUDDLLRDU -4 0 LL -1 -1 DLRLDLUDUR 1 4 URDULUR 0 0 DDUUDUDDDD 0 2 UU 1 0 RRULD 0 -2 LDLRLLDRRL 0 1 RLRLLRLUR -3 0 RL 0 0 D 0 0 L 0 0 DDLRRUDRUD 0 0 DULU 2 0 RR...
output:
UDUDRR UUR Impossible Impossible Impossible UDUUUUURR LRRRRDD UD Impossible LRLRLLDD UDLRLRDD Impossible UDUDRLDDL LL Impossible UDLRUUR Impossible Impossible Impossible LRLRLRLLDD Impossible LR Impossible Impossible Impossible Impossible Impossible LRLRLRRRUU UDLLL Impossible UDUDUDL UDUDRR Impossi...
result:
wrong answer case 396, participant's output goes through forbidden coordinate