結果
問題 |
No.1315 渦巻洞穴
|
ユーザー |
![]() |
提出日時 | 2020-12-12 21:15:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 3,514 bytes |
コンパイル時間 | 812 ms |
コンパイル使用メモリ | 93,160 KB |
最終ジャッジ日時 | 2025-01-16 22:56:35 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 79 |
ソースコード
#include <cmath> #include <cassert> #include <vector> #include <iostream> using namespace std; vector<pair<int, int> > construct_path(int i, int j, int k, int l) { vector<pair<int, int> > path; int dx = i > k ? -1 : 1, dy = j > l ? -1 : 1; while (i != k || j != l) { path.emplace_back(i, j); if (i != k) i += dx; else if (j != l) j += dy; } path.emplace_back(k, l); return path; } int to_val(int x, int y) { int n = max(abs(x), abs(y)); int m = (2 * n + 1) * (2 * n + 1); if (y == -n) return m + x - n; m -= 2 * n; if (x == -n) return m - n - y; m -= 2 * n; if (y == n) return m - x - n; m -= 2 * n; assert(x == n); return m - n + y; } pair<int, int> to_point(int x) { if (x == 1) return {0, 0}; int lb = 0, ub = 23000; while (ub - lb > 1) { int m = (ub + lb) / 2; if ((2 * m + 1) * (2 * m + 1) >= x) ub = m; else lb = m; } int d = x - (2 * ub - 1) * (2 * ub - 1); assert(d >= 0); if (d < 2 * ub) return {ub, - ub + d}; d -= 2 * ub; if (d < 2 * ub) return {ub - d, ub}; d -= 2 * ub; if (d < 2 * ub) return {-ub, ub - d}; d -= 2 * ub; assert(d <= 2 * ub); return {- ub + d, - ub}; } int main() { int s, t; cin >> s >> t; auto [i, j] = to_point(s); auto [k, l] = to_point(t); // cerr << s << ' ' << i << ' ' << j << endl; // cerr << t << ' ' << k << ' ' << l << endl; vector<pair<int, int> > ans; if ((i + j + k + l) % 2 != 0) { vector<pair<int, int> > path = construct_path(i, j, k, l); assert(path.size() % 2 == 0); for (int i = 0; i < path.size(); i += 2) { auto p = path[i], q = path[i+1]; ans.insert(ans.end(), {p, q, p, q}); } } else if ((i + j) % 2 != 0) { vector<pair<int, int> > path1 = construct_path(i, j, 0, 0); vector<pair<int, int> > path2 = construct_path(0, 0, k, l); assert (path1.size() % 2 == 0); assert (path2.size() % 2 == 0); for (int i = 0; i < path1.size(); i += 2) { auto p = path1[i], q = path1[i+1]; ans.insert(ans.end(), {p, q, p, q}); } ans.insert(ans.end(), {{0, 1}, {0, 0}, {1, 0}, {1, 1}, {0, 1}}); for (int i = 0; i < path2.size(); i += 2) { auto p = path2[i], q = path2[i+1]; ans.insert(ans.end(), {p, q, p, q}); } } else { vector<pair<int, int> > path1 = construct_path(i, j, 0, 1); vector<pair<int, int> > path2 = construct_path(0, 1, k, l); assert(path1.size() % 2 == 0); assert(path2.size() % 2 == 0); for (int i = 0; i < path1.size(); i += 2) { auto p = path1[i], q = path1[i+1]; ans.insert(ans.end(), {p, q, p, q}); } ans.insert(ans.end(), {{0, 0}, {1, 0}, {1, 1}}); for (int i = 0; i < path2.size(); i += 2) { auto p = path2[i], q = path2[i+1]; ans.insert(ans.end(), {p, q, p, q}); } } int v = 0; for (auto [x, y] : ans) v ^= to_val(x, y); assert(v == 0); string a; for (int i = 1; i < ans.size(); i++) if (ans[i-1].first < ans[i].first) a.push_back('R'); else if (ans[i-1].first > ans[i].first) a.push_back('L'); else if (ans[i-1].second < ans[i].second) a.push_back('U'); else if (ans[i-1].second > ans[i].second) a.push_back('D'); cout << 0 << endl; cout << a.size() << endl; cout << a << endl; }