Submission #65066715

---

Source Code Expand

#pragma GCC optimize("Ofast","unroll-all-loops","fast-math","no-stack-protector")
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define fi first
#define se second
#if 1
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '['; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "]";}
void _print() {cerr << endl << flush;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define DEBUG(x...) cerr << "*["<<__LINE__<<"]\t"<< #x << " = "; _print(x)
template<class T>
istream& operator>>(istream& is, vector<T>& v) {
	int n; is>>n; v.resize(n);
	for(auto &i:v) is>>i;
	return is;
}
template<class T1,class T2>
istream& operator>>(istream& is, pair<T1,T2>& p) {
	is>>p.fi>>p.se;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for(const auto &i:v) os<<i<<' ';
	return os;
}
template<class T1,class T2>
ostream& operator<<(ostream& os, const pair<T1,T2>& p) {
	os<<p.fi<<' '<<p.se; return os;
}
#endif
 
#define ll long long
#define mp make_pair
#define pb push_back
#define vi vector<ll>
#define pi pair<int, int>
#define L __int128
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}

const int maxn = 105;
ll cnt[maxn][maxn];
int main() {
    int n;
    ll k;
    cin >> n >> k;
    k -= 1;
    cnt[1][1] = k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i + j == 2 * n) break;
            ll ds = 0, rs = 0, cur = cnt[i][j];
            if (i + j <= n) {
                // i * D + j * R
                ll pr = cur / (i + j);
                cur -= pr * (i + j);
                ds += pr * i;
                rs += pr * j;
                for (int m = 1; m <= cur; m++) {
                    if (m <= i) ds++;
                    else rs++;
                }
            }
            else {
                // (n - j) * R + (n - i) * D
                ll pr = cur / (n - i + n - j);
                cur -= pr * (n - i + n - j);
                ds += pr * (n - i);
                rs += pr * (n - j);
                for (int m = 1; m <= cur; m++) {
                    if (m <= n - j) rs++;
                    else ds++;
                }
            }
            cnt[i + 1][j] += ds;
            cnt[i][j + 1] += rs;
        }
    int i = 1, j = 1;
    while (i + j < 2 * n) {
        int mv = 0;
        if (i == n) mv = 1;
        else if (j == n) mv = 0;
        else {
            if (cnt[i + 1][j] <= cnt[i][j + 1]) mv = 0;
            else mv = 1;
        }
        if (mv == 0) {
            i++;
            cout << "D";
        }
        else {
            j++;
            cout << "R";
        }
    }
    cout << endl;
    return 0;
}

Submission Info

Judge Result