結果

問題 No.3162 Five Two Three
ユーザー 👑 Nachia
提出日時 2025-05-23 20:44:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 16 ms / 1,523 ms
コード長 2,984 bytes
コンパイル時間 775 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-23 20:44:29
合計ジャッジ時間 9,571 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 187
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(i64 i=0; i<i64(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
using namespace std;

using i128 = __int128_t;
vector<i128> A1, B1, A2;

void changeAns(vector<i128>& l, vector<i128> r){
    if(l.size() == 0) swap(l, r);
    if(r.size() == 0) return;
    if(l.size() > r.size()) swap(l, r);
}

void testcase(){
    i128 X, Y, Z;
    {
        i64 x, y, z; cin >> x >> z >> y;
        X = x; Y = y; Z = z;
    }
    if(X == 0 && Y == 0 && Z == 0){
        cout << "3\n0 0 0\n";
        return;
    }
    if(X == Y && Y == Z){
        cout << "4\n" << i64(X) << " 0 " << i64(X) << " " << i64(X) << "\n";
        return;
    }

    A1 = {1,0};
    B1 = {0,1};
    rep(f,2){
        while(max(A1.back(), B1.back()) < (1ll << 41)){
            A1.push_back(A1[A1.size() - 1] + A1[A1.size() - 2]);
            B1.push_back(B1[B1.size() - 1] + B1[B1.size() - 2]);
        }
        reverse(A1.begin(), A1.end());
        reverse(B1.begin(), B1.end());
    }
    A2 = {1,0,1,1,0,1};
    rep(f,2){
        while(A2.back() < (1ll << 41)){
            A2.push_back(A2[A2.size() - 1] + A2[A2.size() - 2]);
        }
        reverse(A2.begin(), A2.end());
    }

    bool sw = false;
    if(X == Y){ sw = true; swap(X, Z); }
    vector<i128> ans;
    
    rep(c,A2.size()) rep(b,c) rep(a,b){
        if(A2[a] * Y != A2[b] * X) continue;
        if(A2[a] == 0 && A2[b] == 0) continue;
        i64 q = (A2[a] == 0) ? Y / A2[b] : X / A2[a];
        if(A2[a] * q != X) continue;
        if(A2[b] * q != Y) continue;
        if(A2[c] * q != Z) continue;
        vector<i128> f;
        for(i64 i=a; i<=c; i++) f.push_back(A2[i] * q);
        changeAns(ans, move(f));
    }
    
    rep(c,A1.size()) rep(b,c) rep(a,b){
        i128 x = X * B1[b] - Y * B1[a];
        i128 y = A1[a] * Y - A1[b] * X;
        i128 d = A1[a] * B1[b] - A1[b] * B1[a];
        if(d < 0){ x = -x; y = -y; d = -d; }
        if(d == 0) continue;
        if(x % d != 0 || x < 0) continue;
        if(y % d != 0 || y < 0) continue;
        x /= d; y /= d;
        if(Z != A1[c] * x + B1[c] * y) continue;
        vector<i128> f;
        for(i64 i=a; i<=c; i++) f.push_back(A1[i] * x + B1[i] * y);
        bool ok = true;
        for(auto g : f) if(g < 0) ok = false;
        if(ok) changeAns(ans, move(f));
    }

    if(sw) reverse(ans.begin(), ans.end());

    if(ans.size() == 0){
        cout << "-1\n";
    } else {
        cout << ans.size() << "\n";
        rep(i,ans.size()){
            if(i) cout << " ";
            cout << i64(ans[i]);
        } cout << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    testcase();
    return 0;
}
0