結果

問題 No.1315 渦巻洞穴
コンテスト
ユーザー t33f
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0