Submission #65067729

---

Source Code Expand

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
ll v[105];
vector<vector<ll>> calc(int n,ll k)
{
	vector<vector<ll>> vd(n+1);
	vector<vector<ll>> cnt(n+1);
	cnt[1]={k};
	vd[1]={};
	v[1]=1;
	for(int i=2;;i++)
	{
		longer x=(longer)(i)/__gcd((ll)(i),v[i-1])*v[i-1];
		if(x>3e18) break;
		v[i]=x;
	}
	for(int i=2;i<=n;i++)
	{
		// int ins;
		// if(i==2) ins=k%2;
		// else if(!v[i]) ins=0;
		// else
		// {
		// 	ll x=v[i]/3;
		// 	ll vv=k%v[i];
		// 	if(!vv) vv=v[i];
		// 	if(vv>=x&&vv<=x+x) ins=1;
		// 	else ins=0;
		// }
		for(int ins=0;ins<2&&!sz(cnt[i]);ins++)
			for(int j=0;j<=sz(vd[i-1]);j++)
			{
				vd[i]=vd[i-1];
				vd[i].insert(vd[i].begin()+j,ins);
				vector<ll> val(i);
				for(int x=i-2;x>=0;x--)
					val[x]=val[x+1]+vd[i][x];
				ll sum=accumulate(ALL(val),0ll);
				if(sum%i!=k%i) continue;
				for(auto &x:val) x+=(k-sum)/i;
				cnt[i]=val;
				break;
			}
	}
	return cnt;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	ll k;
	cin>>n>>k;
	vector<vector<ll>> A=calc(n,k),B=calc(n,k-1);
	vector<int> vp;
	for(int i=1;i<=n;i++)
		for(int j=0;j<i;j++)
			if(A[i][j]!=B[i][j])
				vp.pb(j);
	string ans;
	for(int i=1;i<sz(vp);i++)
		if(vp[i]!=vp[i-1])
			ans+='R';
		else
			ans+='D';
	string t=ans;
	rev(t);
	for(auto &ch:t) ch='R'+'D'-ch;
	ans+=t;
	cout<<ans<<'\n';
	return 0;
}

Submission Info

Judge Result