結果
問題 | No.2411 Reverse Directions |
ユーザー | 👑 Nachia |
提出日時 | 2023-08-11 22:08:25 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,736 bytes |
コンパイル時間 | 1,132 ms |
コンパイル使用メモリ | 96,956 KB |
実行使用メモリ | 12,016 KB |
最終ジャッジ日時 | 2024-11-18 16:30:35 |
合計ジャッジ時間 | 3,037 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 9 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,816 KB |
testcase_06 | AC | 2 ms
6,820 KB |
testcase_07 | AC | 5 ms
7,552 KB |
testcase_08 | AC | 1 ms
6,816 KB |
testcase_09 | AC | 2 ms
6,816 KB |
testcase_10 | AC | 20 ms
12,016 KB |
testcase_11 | AC | 2 ms
6,820 KB |
testcase_12 | AC | 22 ms
9,252 KB |
testcase_13 | AC | 2 ms
6,824 KB |
testcase_14 | AC | 8 ms
6,820 KB |
testcase_15 | AC | 4 ms
6,820 KB |
testcase_16 | AC | 2 ms
6,816 KB |
testcase_17 | AC | 7 ms
6,820 KB |
testcase_18 | AC | 5 ms
6,820 KB |
testcase_19 | AC | 2 ms
6,820 KB |
testcase_20 | AC | 7 ms
6,816 KB |
testcase_21 | AC | 2 ms
6,816 KB |
testcase_22 | WA | - |
testcase_23 | AC | 2 ms
6,820 KB |
testcase_24 | AC | 19 ms
9,568 KB |
testcase_25 | AC | 2 ms
6,820 KB |
testcase_26 | AC | 2 ms
6,820 KB |
testcase_27 | AC | 2 ms
6,820 KB |
testcase_28 | AC | 14 ms
6,816 KB |
testcase_29 | AC | 22 ms
9,036 KB |
testcase_30 | AC | 18 ms
7,892 KB |
testcase_31 | AC | 2 ms
6,820 KB |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <tuple> #include <atcoder/modint> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; int main(){ int H,W,K,L,R; cin >> H >> W >> K >> L >> R; L--; vector<string> G(H); rep(y,H) cin >> G[y]; if((R-L) % 2 == 1){ cout << "No\n"; return 0; } if((H+W)%2 != K%2){ cout << "No\n"; return 0; } tuple<int, int, char, int> dir[4] = {{1,0,'D',0},{-1,0,'U',1},{0,1,'R',2},{0,-1,'L',3}}; auto getdist = [&](int sy, int sx){ vector<pair<int,int>> que; vector pre(H, vector(W,-1)); pre[sy][sx] = -2; vector dist(H, vector(W,K+1)); dist[sy][sx] = 0; que.push_back({sy,sx}); rep(i,que.size()){ auto [y,x] = que[i]; for(auto [dy,dx,c,di] : dir){ int nx = x + dx, ny = y + dy; if(nx < 0 || ny < 0 || nx >= W || ny >= H) continue; if(G[ny][nx] == '#') continue; if(pre[ny][nx] != -1) continue; pre[ny][nx] = di; dist[ny][nx] = dist[y][x] + 1; que.push_back({ ny,nx }); } } return make_pair(move(dist), move(pre)); }; auto getpath = [&](int sy, int sx, int ty, int tx, const vector<vector<int>>& pre){ vector<int> res; while(sy != ty || sx != tx){ auto [dy,dx,c,di] = dir[pre[ty][tx]]; res.push_back(di); ty -= dy; tx -= dx; } return res; }; auto [dist0, pre0] = getdist(0,0); auto [dist1, pre1] = getdist(H-1,W-1); int ty=-1, tx=-1, td=-1; for(int y=0; y<H; y++) for(int x=0; x<W; x++) if(dist0[y][x] <= L && dist1[y][x] <= K-R){ if(y!=0 && y!=H-1 && G[y-1][x] != '#' && G[y+1][x] != '#'){ ty=y; tx=x; td=0; break; } if(x!=0 && x!=W-1 && G[y][x-1] != '#' && G[y][x+1] != '#'){ ty=y; tx=x; td=2; break; } } if(ty < 0){ cout << "No\n"; return 0; } auto p0 = getpath(0, 0, ty, tx, pre0); auto p1 = getpath(H-1, W-1, ty, tx, pre1); reverse(p0.begin(), p0.end()); int cnt = K - p0.size() - p1.size(); rep(i,cnt) p0.push_back(td ^ (i%2)); for(int x : p1) p0.push_back(x^1); cout << "Yes\n"; rep(i,p0.size()){ cout << (char)get<2>(dir[p0[i]]); } cout << '\n'; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;