#include using namespace std; #include using namespace atcoder; using ll = long long; using P = pair; using TUP = tuple; map state_idx; int N; int dx[] = {1,0,-1,0}; int dy[] = {0,1,0,-1}; string ds = "DRUL"; string buff; vector

phistory; int roopst = -1; void dfs(TUP cur,int turn){ if(state_idx.count(cur)&&turn%4==0){ auto [nxp,nxg] = cur; //cout<(cur)); for(int i= 0;i<4;i++){ auto [nxp,nxg] = cur; nxp.first += dx[i]; nxp.second += dy[i]; if(nxp.first<0||nxp.first>=5)continue; if(nxp.second<0||nxp.second>=5)continue; if(turn%4==3){ nxg = phistory[turn/4*4]; } if(nxp.first==nxg.first||nxp.second==nxg.second){ continue; } TUP nx(nxp,nxg); buff.push_back(ds[i]); dfs(nx,turn+1); if(roopst!=-1)break; buff.pop_back();; } phistory.pop_back(); state_idx.erase(cur); } void solve(){ auto cur = TUP(P(0,0),P(-1,-1)); dfs(cur,0); ll loopsize = buff.size()-roopst; string loop = buff.substr(roopst,loopsize); while(buff.size()> N; solve(); }