QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351806 | #6422. Evil Coordinate | PorNPtree# | AC ✓ | 8ms | 3740kb | C++20 | 2.3kb | 2024-03-12 15:11:27 | 2024-03-12 15:11:28 |
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;}
}t=g[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) 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: 3592kb
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: 0
Accepted
time: 8ms
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:
ok 11109 cases
Test #3:
score: 0
Accepted
time: 4ms
memory: 3740kb
input:
11107 1 0 LLRLRURLR 1 0 LLRR 0 1 R 1 0 LLLRLRRR 1 0 RUL 0 1 UD 1 0 RLRLU 0 1 DDDUUUDU 1 0 RURRLLRLL 1 0 LRLR 1 0 ULR 0 1 R 0 1 DDUUUDR 0 1 UUDDUDDU 0 1 DDUUDU 1 0 RRLRLLRLRL 1 0 RLRRLL 1 0 LUR 1 0 U 1 0 LRRRLLLR 0 1 DRUUDDUDU 0 1 DUUDDUR 1 0 LRLRLR 0 1 UUDDDUDU 0 1 R 0 1 UDUDDU 0 1 DUUDUD 1 0 RRLRRR...
output:
LRLRLRLRU LRLR R LRLRLRLR LRU DU LRLRU DUDUDUDU LRLRLRLRU LRLR LRU R DUDUDUR DUDUDUDU DUDUDU LRLRLRLRLR LRLRLR LRU U LRLRLRLR DUDUDUDUR DUDUDUR LRLRLR DUDUDUDU R DUDUDU DUDUDU LRLRLRLRLR DUDUDUDU DUDU LRLRLRLRU DUDU LRLRLR LRU LRU U LRU LRLRLR LRLRLRLRLR U DUDUDU R LRLRLR DUDUDUDUR DUDUDUDUR LRLRLR ...
result:
ok 11107 cases