結果

問題 No.3162 Five Two Three
ユーザー kencho
提出日時 2025-05-05 00:22:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,002 bytes
コンパイル時間 2,144 ms
コンパイル使用メモリ 214,872 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-05 01:36:30
合計ジャッジ時間 8,846 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 78 WA * 109
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128  = __int128_t;

static inline i128 key(int64 a, int64 b){ return (i128(a) << 64) | (uint64_t)b; }

// 各 pair (pre,cur) の情報
struct Node{
    int64 pre, cur;
    i128  par;        // 親 pair の key (root だけ -1)
    bool  usedZ;
};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int64 X, Y, Z;  if(!(cin >> X >> Y >> Z)) return 0;

    /* --- 3 項で済む？ --- */
    if (llabs(X - Y) == Z){
        cout << 3 << '\n' << X << ' ' << Z << ' ' << Y << '\n';
        return 0;
    }

    /* --- Z = 0 で片端が 0 のときは長さ 5 で決着 --- */
    if (Z == 0){
        if (X == 0 && Y == 0){
            cout << 3 << "\n0 0 0\n";                 return 0;
        }
        if (X == 0){
            cout << 5 << '\n' << 0 << ' ' << Y << ' ' << Y << ' ' << 0 << ' ' << Y << '\n';
            return 0;
        }
        if (Y == 0){
            cout << 5 << '\n' << X << " 0 " << X << ' ' << X << " 0\n";
            return 0;
        }
    }

    /* ---------- 双方向反復深化 ----------- */
    const int MAXD = 90;               // 10^12 ならこれで十分
    for (int D = 4; D <= MAXD; ++D){
        int Llim = D / 2, Rlim = D - Llim;

        unordered_map<i128, Node> L, R;
        queue<Node> qL, qR;

        // 左側の root  (dummy_pre, X)
        int64 dummyL = (X == 0 ? 1 : 0);
        Node rootL { dummyL, X, -1, (X == Z) };
        qL.push(rootL);  L.emplace(key(dummyL, X), rootL);

        // 右側の root  (Y, dummy_suf)
        int64 dummyR = (Y == 0 ? 1 : 0);
        Node rootR { Y, dummyR, -1, (Y == Z) };
        qR.push(rootR);  R.emplace(key(Y, dummyR), rootR);

        auto expand = [&](queue<Node>& Q, unordered_map<i128,Node>& mp,
                          int lim){
            while(!Q.empty() && (int)mp.size() <= (1<<22)){   // 軽い安全弁
                Node cur = Q.front();  if (--lim < 0) break;  Q.pop();
                int64 a = cur.pre, b = cur.cur;

                for(int s = 0; s < 2; ++s){
                    int64 c = (s ? llabs(a - b) : a + b);
                    if (c < 0 || c > 1000000000000LL) continue;
                    i128 k = key(b, c);
                    if (mp.count(k)) continue;

                    Node nxt { b, c, key(a, b),
                               cur.usedZ || (c == Z) };
                    mp.emplace(k, nxt);
                    Q.push(nxt);
                }
            }
        };

        expand(qL, L, Llim);
        expand(qR, R, Rlim);

        /* --- 衝突検出 --- */
        for (auto &kv : L){
            auto &ln = kv.second;             // (p,q)
            int64 p = ln.pre, q = ln.cur;

            auto it = R.find(key(q, p));      // (q,r) があるか？
            if (it == R.end()) continue;

            auto &rn = it->second;            // (q,r)
            int64 r = rn.cur;
            if ( llabs(p - r) != q ) continue;
            if ( !(ln.usedZ || rn.usedZ) ) continue;   // Z を含まない

            /* ---- 経路復元 ---- */
            vector<int64> left, right;

            // 左側（X → … → q）: cur を辿る
            for (i128 k = key(p,q); k != -1; k = L[k].par){
                left.push_back(L[k].cur);
            }
            reverse(left.begin(), left.end());     // X から q へ

            // 右側（q → … → Y）: cur を辿る
            for (i128 k = key(q,r); k != -1; k = R[k].par){
                if (k != key(q,r))   // q は重複させない
                    right.push_back(R[k].cur);
            }

            /* 出力 */
            vector<int64> ans = left;
            ans.insert(ans.end(), right.begin(), right.end());

            cout << ans.size() << '\n';
            for (size_t i = 0; i < ans.size(); ++i){
                cout << ans[i] << (i + 1 == ans.size() ? '\n' : ' ');
            }
            return 0;
        }
    }
    cout << -1 << '\n';
    return 0;
}
0