結果
問題 | No.2228 Creeping Ghost |
ユーザー |
|
提出日時 | 2023-02-24 23:34:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,611 bytes |
コンパイル時間 | 3,444 ms |
コンパイル使用メモリ | 261,624 KB |
最終ジャッジ日時 | 2025-02-10 22:51:32 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 |
ソースコード
#include<bits/stdc++.h>using namespace std;#include<atcoder/all>using namespace atcoder;using ll = long long;using P = pair<int,int>;using TUP = tuple<P,P>;map<TUP,int> state_idx;int N;int dx[] = {1,0,-1,0};int dy[] = {0,1,0,-1};string ds = "DRUL";string buff;vector<P> phistory;int roopst = -1;void dfs(TUP cur,int turn){if(state_idx.count(cur)&&turn%4==0){auto [nxp,nxg] = cur;//cout<<nxp.first<<' '<<nxp.second<<' '<<nxg.first<<' '<<nxg.second<<endl;roopst = state_idx[cur];if(roopst%4==0){return;}else{roopst=-1;}}state_idx[cur] = buff.size();phistory.push_back(get<0>(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){buff+=loop;}int x=0,y=0;/*for(int i = 0;i<N;i++){if(buff[i]=='U')x--;if(buff[i]=='D')x++;if(buff[i]=='R')y++;if(buff[i]=='L')y--;}*///cout<<buff.substr(0,roopst)<<endl;//cout<<loop<<endl;//cout<<x<<' '<<y<<endl;cout<<buff.substr(0,N)<<endl;}signed main(){cin.tie(nullptr);ios::sync_with_stdio(false);cin >> N;solve();}