結果

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

ソースコード

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;

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

struct Node{
    int64 pre,cur;
    i128  par;         // -1 は root
    uint8_t depth;
    bool hasZ;
};

void expand(queue<i128>& Q, unordered_map<i128,Node>& mp,
            int64 Z){
    size_t sz=Q.size();
    while(sz--){
        i128 k=Q.front(); Q.pop();
        auto 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=key(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);
        }
    }
}

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

    if(llabs(X-Y)==Z){
        cout<<3<<"\n"<<X<<" "<<Z<<" "<<Y<<"\n"; return 0;
    }

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

    int64 dL=(X==0?1:0), dR=(Y==0?1:0);
    i128 kL=key(dL,X), kR=key(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);

    for(int dep=1; dep<=MAX_DEPTH; ++dep){
        if(qL.size()<=qR.size()) expand(qL,L,Z);
        else                     expand(qR,R,Z);

        const auto &S=(L.size()<R.size()?L:R);
        const auto &T=(L.size()<R.size()?R:L);

        for(auto &kv:S){
            const auto &ln=kv.second;          // (p,q)
            int64 p=ln.pre,q=ln.cur;
            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(key(q,r));
                if(it==T.end()) continue;
                const auto &rn=it->second;
                if(!(ln.hasZ||rn.hasZ||q==Z||r==Z)) continue;

                /* ---------- 復元 ---------- */
                vector<int64> left,right,ans;
                for(i128 k=kv.first;k!=-1;k=L.at(k).par)
                    left.push_back(L.at(k).cur);
                reverse(left.begin(),left.end());

                vector<const Node*> chain;
                for(i128 k=it->first; ; ){
                    chain.push_back(&T.at(k));
                    if(T.at(k).par==-1) break;
                    k=T.at(k).par;
                }
                right.push_back(chain[0]->cur);
                for(size_t i=1;i<chain.size();++i)
                    right.push_back(chain[i]->pre);
                if(right.back()!=Y) right.push_back(Y);   // ★修正ポイント★

                ans.reserve(left.size()+right.size());
                ans.insert(ans.end(),left.begin(),left.end());
                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";
}
0