結果

問題 No.3162 Five Two Three
ユーザー kencho
提出日時 2025-05-05 00:11:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,467 bytes
コンパイル時間 2,239 ms
コンパイル使用メモリ 212,564 KB
実行使用メモリ 53,680 KB
最終ジャッジ日時 2025-05-05 01:36:22
合計ジャッジ時間 6,236 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1 TLE * 1
other -- * 187
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
struct Node{
    int64 pre,cur;      // (A_{i-1}, A_i)
    uint8_t usedZ;      // Z を含んだ？ 0/1
    uint8_t lastOp;     // 0:+ 1:-
};
// key には (pre<<64)|cur を詰め込む
static inline __uint128_t key(int64 a,int64 b){ return (__uint128_t(a)<<64)+ (__uint128_t)b; }

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

    /* --- 長さ3 で終了出来るか --- */
    if (abs(X-Y)==Z){
        cout<<3<<"\n"<<X<<" "<<Z<<" "<<Y<<"\n";
        return 0;
    }

    /* --- 双方向反復深化 IDA* --- */
    const int MAXDEP = 90;          // 10^12 を超えるのに十分
    for(int depth=4; depth<=MAXDEP; ++depth){
        int l = depth/2, r = depth - l;

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

        // 左側 root
        qL.push({0,X, 0, 0});          // 仮想値 0 ← X から開始（長さの偶奇を吸収するダミー）
        // 右側 root
        qR.push({0,Y, 0, 0});

        L.reserve(1<<20); R.reserve(1<<20);

        auto expand=[&](queue<Node>&q, unordered_map<__uint128_t,Node>&mp,
                        int lim, bool isLeft){
            while(!q.empty() && q.front().lastOp < lim){
                auto cur = q.front(); q.pop();
                int64 a = cur.pre, b = cur.cur;

                for(int s=0; s<2; ++s){
                    int64 c = s==0 ? a+b : llabs(a-b);
                    if(c<0 || c>1000000000000LL) continue;
                    Node nxt{b,c, (cur.usedZ||(c==Z)||(b==Z)), uint8_t(cur.lastOp+1)};
                    auto k = key(b,c);
                    if(!mp.count(k)){
                        mp.emplace(k,nxt);
                        q.push(nxt);
                    }
                }
            }
        };

        expand(qL,L,l,true);
        expand(qR,R,r,false);

        /* --- 衝突判定 --- */
        for(auto &kv:L){
            int64 p = kv.second.pre, qv = kv.second.cur;
            auto it = R.find(key(qv,p));    // 後ろ側のペアは (qv, ?)
            if(it==R.end()) continue;
            int64 r = it->second.cur;
            if( (llabs(p - r)==qv) && (kv.second.usedZ || it->second.usedZ) && Z!=X && Z!=Y){
                /* 復元 */
                vector<int64> left, right;
                // 左列（逆に取る）
                auto tmp = kv.second;
                left.push_back(tmp.cur); left.push_back(tmp.pre);
                while(tmp.lastOp){
                    auto parKey = key(tmp.pre, tmp.cur);      // 同じ key
                    tmp = L[parKey];                          // 親は pre,cur が 1 つ前
                    left.push_back(tmp.pre);
                }
                reverse(left.begin(), left.end());
                // 右列
                tmp = it->second;
                right.push_back(tmp.cur);
                while(tmp.lastOp){
                    auto parKey = key(tmp.pre, tmp.cur);
                    tmp = R[parKey];
                    right.push_back(tmp.cur);
                }
                // 連結
                left.insert(left.end(), right.begin(), right.end());

                cout<<left.size()<<"\n";
                for(size_t i=1;i<left.size();++i) cout<<left[i-1]<<" ";
                cout<<left.back()<<"\n";
                return 0;
            }
        }
    }
    cout<<-1<<"\n";
    return 0;
}
0