結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128  = __int128_t;
const int64 LIM = 1'000'000'000'000LL;
const int  MAX_DEPTH = 35;            // 単純 BFS で現実的に耐えられる限界付近

/* キー圧縮 ───────────── */
static inline i128 pack(int64 a, int64 b){ return (i128(a)<<64) | (uint64_t)b; }

/* 探索ノード ─────────── */
struct Node{
    int64 pre, cur;
    i128  par;        // 親のキー（root は -1）
    uint8_t depth;    // root からの深さ
    bool hasZ;        // ここまでに Z を見たか
};

/* 片側フロンティアを 1 層広げる */
void expand_layer(queue<i128>& q,
                  unordered_map<i128,Node>& mp,
                  int64 Z)
{
    size_t layer_sz = q.size();
    while(layer_sz--){
        i128 k = q.front(); q.pop();
        Node nd = mp[k];
        int64 a = nd.pre, b = nd.cur;

        int64 nxt[2] = {a + b, llabs(a - b)};
        for(int t=0;t<2;++t){
            int64 c = nxt[t];
            if(c<0 || c>LIM) continue;
            i128 nk = pack(b,c);
            if(mp.count(nk)) continue;
            mp.emplace(nk, Node{b,c,k, uint8_t(nd.depth+1),
                                nd.hasZ || (c==Z)});
            q.push(nk);
        }
    }
}

/* 復元して出力 */
void output_path(i128 meetL, i128 meetR,
                 const unordered_map<i128,Node>& L,
                 const unordered_map<i128,Node>& R)
{
    vector<int64> left, right;

    /* 左列：cur を取りながら root へ */
    for(i128 k=meetL; k!=-1; k=L.at(k).par)
        left.push_back(L.at(k).cur);
    reverse(left.begin(), left.end());

    /* 右列：cur を取りながら root へ。ただし重複する q を除く */
    bool first = true;
    for(i128 k=meetR; k!=-1; k=R.at(k).par){
        if(first){                    // (q,r) の r だけ
            right.push_back(R.at(k).cur);
            first=false;
        }else{                       // 以降は pre を採用
            right.push_back(R.at(k).pre);
        }
    }

    /* 結合して表示 */
    left.insert(left.end(), right.begin(), right.end());
    cout<<left.size()<<"\n";
    for(size_t i=0;i<left.size();++i)
        cout<<left[i]<<(i+1==left.size()?'\n':' ');
}

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

    /* 両端が 0,0,1 などの超簡単ケースはスキップ
       （BFS でも瞬時に解けるので敢えて条件分岐しない） */

    /* 初期化 ------------------------------------------------------- */
    unordered_map<i128,Node> L, R;
    queue<i128> qL, qR;

    int64 dL = (X==0?1:0);
    int64 dR = (Y==0?1:0);

    i128 kL = pack(dL,X);
    i128 kR = pack(Y,dR);

    L.emplace(kL, Node{dL,X,-1,0,(dL==Z)||(X==Z)});
    R.emplace(kR, Node{Y,dR,-1,0,(Y==Z)||(dR==Z)});

    qL.push(kL);
    qR.push(kR);

    /* 双方向 BFS ---------------------------------------------------- */
    for(int depth=1; depth<=MAX_DEPTH; ++depth){
        /* 小さい方のフロンティアを拡張 */
        if(qL.size() <= qR.size()){
            expand_layer(qL,L,Z);
        }else{
            expand_layer(qR,R,Z);
        }

        /* 衝突検査：小さい map から大きい map へ */
        const auto &S = (L.size() < R.size()) ? L : R;
        const auto &T = (L.size() < R.size()) ? R : L;
        for(const auto &kv : S){
            const Node &nd = kv.second;        // (p,q)
            int64 p = nd.pre, q = nd.cur;

            /* r は p±q の 2 通りだけ */
            int64 cand[2] = { llabs(p-q), p+q };
            for(int t=0;t<2;++t){
                int64 r = cand[t];
                if(r<0 || r>LIM) continue;
                auto it = T.find(pack(q,r));
                if(it==T.end()) continue;

                const Node &nd2 = it->second;  // (q,r)
                if(!(nd.hasZ || nd2.hasZ || q==Z || r==Z)) continue;

                /* 左右どちらが S/T かで meetL/meetR を決める */
                i128 meetL, meetR;
                if(&S==&L){ meetL = kv.first; meetR = it->first; }
                else      { meetL = it->first; meetR = kv.first; }

                output_path(meetL, meetR, L, R);
                return 0;
            }
        }
    }

    cout<<-1<<"\n";
    return 0;
}
0