結果
問題 | No.2228 Creeping Ghost |
ユーザー | ttkkggww |
提出日時 | 2023-02-24 23:13:05 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,686 bytes |
コンパイル時間 | 4,554 ms |
コンパイル使用メモリ | 274,284 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-13 06:04:12 |
合計ジャッジ時間 | 6,189 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
ソースコード
#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; 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]; return; } state_idx[cur] = turn; 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){ auto tmp = get<0>(cur); for(int i = 0;i<3;i++){ auto move = buff[buff.size()-1-i]; if(move=='U')tmp.first++; if(move=='D')tmp.first--; if(move=='L')tmp.second++; if(move=='R')tmp.second--; } nxg = tmp; } 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();; } 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(); }