ABC 454 E
Sora
c_cpp
2 months ago
1.7 kB
6
Indexable
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll mod = 1e9+7;
void solve(){
ll n, a, b; cin >> n >> a >> b;
// if N odd or (A+B) even -> NOT POSSIBLE
if ((n & 1) || !((a+b) & 1)) {cout << "No\n"; return;}
cout << "Yes\n";
// keep reducing boundaries by 4 possible ways ensuring top left is start and bottom right is end. Reduce until 2x2. Easy to solve 2x2.
ll l = 1, r = n, u = 1, d = n;
vector<string> st, ed;
while (r - l > 1 || d - u > 1){
if (a - u >= 2){ // a
st.push_back(string(r-l, 'R') + "D" + string(r-l, 'L') + "D");
u += 2;
} else if (d - a >= 2){ // c
ed.push_back("D" + string(r-l, 'L') + "D" + string(r-l, 'R'));
d -= 2;
} else if (b - l >= 2){ // b
st.push_back(string(d-u, 'D') + "R" + string(d-u, 'U') + "R");
l += 2;
} else { // d
ed.push_back("R" + string(d-u, 'U') + "R" + string(d-u, 'D'));
r -= 2;
}
}
reverse(ed.begin(), ed.end());
for (string& s : st) cout << s;
cout << (a == u && b == r ? "DR" : "RD");
for (string& s : ed) cout << s;
cout << '\n';
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
ll t; cin >> t;
while (t--) solve();
}
// TC - O(N*N) due to moves
// SC - O(N*N) due to moves
// N^2 - 2 movesEditor is loading...
Leave a Comment