結果
| 問題 |
No.3162 Five Two Three
|
| ユーザー |
 jastaway
|
| 提出日時 | 2025-05-06 23:28:02 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 182 ms / 1,523 ms |
| コード長 | 13,656 bytes |
| コンパイル時間 | 6,268 ms |
| コンパイル使用メモリ | 333,788 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-06 23:28:42 |
| 合計ジャッジ時間 | 33,104 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 187 |
ソースコード
#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
// #include <boost/rational.hpp>
// using namespace boost;
// using rat = rational<long long int>;
using mint = modint998244353;
// using mint = modint1000000007;
// using mint = mint;
using ll = long long;
using ld = long double;
using ull = uint64_t;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vm = vector<mint>;
using vvm = vector<vm>;
using vvvm = vector<vvm>;
using vstr = vector<string>;
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
#define vvv(T) vector<vector<vector<T>>>
#define vvvv(T) vector<vector<vector<vector<T>>>>
istream &operator>>(istream &is, mint &a){ll tmp; is >> tmp; a = tmp; return is;}
ostream &operator<<(ostream &os, const mint &a){ os << a.val(); return os; }
string to_string(const __int128_t &a) { if (a == 0) return "0"; string s = ""; __int128_t num = a; bool is_negative = false; if (num < 0) { is_negative = true; num = -num; } while (num > 0) { s += '0' + (num % 10); num /= 10; } if (is_negative) s += '-'; reverse(s.begin(), s.end()); return s; }
istream &operator>>(istream &is, __int128_t &a){ string s; is >> s; a = 0; for(char c : s) { if(isdigit(c)) {a = a*10 + (c - '0'); } } if(s[0]=='-'){ a *= -1; } return is; }
ostream &operator<<(ostream &os, const __int128_t &a){ os << to_string(a); return os; }
template<class T, class U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<class T> istream &operator>>(istream &is, vector<T> &vec){ for(T &e : vec){is >> e;} return is; }
template<class T> ostream &operator<<(ostream &os, const vector<T> &vec) { for(int i = 0; i < (int)vec.size(); i++) { os << vec[i] << (i + 1 != (int)vec.size() ? " " : ""); } return os; }
template <class... T> constexpr auto min (T... a) { return min(initializer_list<common_type_t<T...>>{a...}); }
template <class... T> constexpr auto max (T... a) { return max(initializer_list<common_type_t<T...>>{a...}); }
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template<class T> T opmin(T x, T y) { return min(x, y); }
template<class T> T einf() { return numeric_limits<T>::max(); }
template<class T> T opmax(T x, T y) { return max(x, y); }
template<class T> T eminf() { return numeric_limits<T>::min(); }
template<class T> T opsum(T x, T y) { return x + y; }
template<class T> T ezero() { return (T)0; }
// #define maxseg(T) segtree<T, [](T x, T y){return max(x, y);}, [](){return (T)(-(1LL << 60));}>
// #define minseg(T) segtree<T, [](T x, T y){return min(x, y);}, [](){return (T)((1LL << 60));}>
// #define sumseg(T) segtree<T, [](T x, T y){return x + y;}, [](){return (T)(0);}>
template<class T> using minseg = segtree<T, opmin<T>, einf<T>>;
template<class T> using maxseg = segtree<T, opmax<T>, eminf<T>>;
template<class T> using sumseg = segtree<T, opsum<T>, ezero<T>>;
// template<class T> struct v : vector<T> { using vector<T> :: vector; };
// template<class T> struct vv : vector<v<T>> { using vector<v<T>> :: vector; };
// template<class T> struct vvv : vector<vv<T>> { using vector<vv<T>> :: vector; };
template<class T> inline bool chmin(T& a, T b) {if(a > b){a = b; return true;} else {return false;}};
template<class T> inline bool chmax(T& a, T b) {if(a < b){a = b; return true;} else {return false;}};
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i,n) for(ll i = (ll)(n) - 1; i >= 0; i--)
#define REP(i, l, r) for(ll i = (ll)l; i <= (ll)(r); i++)
#define REPR(i, l, r) for(ll i = (ll)r; i >= (ll)(l); i--)
const ll inf = (1 << 30);
const ll INF = (1LL << 60);
const vector<pair<ll, ll>> DIJ = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
void out(){cout<<'\n';}
template<class T, class... Ts> void out(const T& a, const Ts&... b){ cout<<a; (cout<<... << (cout << ' ', b)); cout << '\n';}
void outf(){cout<<endl;}
template<class T, class... Ts> void outf(const T& a, const Ts&... b){ cout<<a; (cout<<... << (cout << ' ', b)); cout << endl;}
template<class T, class U> void outp(pair<T, U> a){ out((a).first, (a).second); }
template<class T, class U> void outpf(pair<T, U> a){ outf((a).first, (a).second); }
template<class T> void outv(T a){rep(i, (a).size()){ cout << (a)[i] << " "; } cout << endl;}
template<class T> void outvL(T a){rep(i, (a).size()){out((a)[i]);} cout << flush; }
// template<class T> void outvv(T a){rep(i, a.size()){ rep(j, a.at(i).size()){cout << a.at(i).at(j) << " "; } cout << endl; }}
// template<class T> void outvp(T a){rep(i, a.size()){ out2(a.at(i).first, a.at(i).second); }}
void setpre(int a){cout << fixed << setprecision(a);}
#define outN out("No")
#define outY out("Yes")
#define outYN(flag) out(flag ? "Yes" : "No")
#define dame(...) {outf(__VA_ARGS__);return 0;}
template<class T> void read(vector<T>& vec){ for(int i = 0; i < (int)vec.size(); i++) { cin >> vec[i]; } }
template<class... T> void read(T&... a){(cin >> ... >> a);}
#define readll(...) ll __VA_ARGS__; read(__VA_ARGS__)
#define readvll(a, n) vector<ll> a(n); read(a)
#define readvt(type, a, n) vector<type> a(n); read(a)
#define readvll2(a, b, n) vector<ll> a(n), b(n); for(int lopi = 0; lopi < (int)(n); lopi++) cin >> (a)[lopi] >> (b)[lopi]
#define readvll3(a, b, c, n) vector<ll> a(n), b(n), c(n); for(int lopi = 0; lopi < (int)(n); lopi++) cin >> (a)[lopi] >> (b)[lopi] >> (c)[lopi]
#define readstr(...) string __VA_ARGS__; read(__VA_ARGS__)
#define readundirG(G, N, M) G = vvll(N); rep(lopi, M) {ll a, b; cin >> a >> b; G[a-1].push_back(b-1); G[b-1].push_back(a-1);}
#define readdirG(G, N, M) G = vvll(N); rep(lopi, M) {ll a, b; cin >> a >> b; G[a-1].push_back(b-1);}
#define readundirwghG(G, N, M) G = vv(pll)(N); rep(lopi, M) {ll a, b, c; cin >> a >> b >> c; G[a-1].emplace_back(b-1,c); G[b-1].emplace_back(a-1, c);}
#define readdirwghG (G, N, M) G = vv(pll)(N); rep(lopi, M) {ll a, b, c; cin >> a >> b >> c; G[a-1].emplace_back(b-1, c);}
#define All(a) (a).begin(), (a).end()
template<class T> inline void sortr(T& a){ sort((a).rbegin(), (a).rend()); }
template<class T> inline vector<int> argsort(T V, bool rev = false){vector<int> res(V.size()); iota(res.begin(), res.end(), 0); sort(res.begin(), res.end(), [&](int x, int y){if(!rev){return V[x] < V[y];}else{return V[x] > V[y];}}); return res;}
template<class T, class U> inline void sort_by_idx(T& V, vector<U>& I){assert(V.size() == I.size()); T tmpv = V; for(int loopi = 0; loopi < (int)I.size(); loopi++){V[loopi] = tmpv[I.at(loopi)];}}
template<class T, class U> inline void sortp(vector<T>& v1, vector<U>& v2, bool rev1 = false, int rev2 = false){assert(v1.size() == v2.size()); vector<int> I(v1.size()); iota(I.begin(), I.end(), 0); sort(I.begin(), I.end(), [&](const int x, const int y){if(v1[x] != v1[y]){return (bool)(rev1 ^ (v1[x] < v1[y]));}else{if(v2[x]==v2[y]){return false;} return (bool)(rev2 ^ (v2[x] < v2[y]));}}); sort_by_idx(v1, I); sort_by_idx(v2, I);}
template<class T> T POW(T x, ll n) {T ret = 1; while(n > 0){if(n & 1) ret *= x; x *= x; n >>= 1;} return ret;}
ll powll(ll x, ll n){ll ret = 1; while(n > 0){if(n & 1) ret *= x; x *= x; n >>= 1;} return ret;}
inline ll divceil(ll x, ll y) { if(x >= 0) {return(x / y + (ll)(x % y != 0)); } else { return -((-x) / y); } }
inline ll divfloor(ll x, ll y) { if(x >= 0) { return x/y; } else { return -((-x)/y + (ll)((-x) % y != 0)); } }
inline bool inLR(ll x, ll L, ll R){ return (L <= x && x < R); }
inline bool inRect(ll pos_x, ll pos_y, ll rect_H, ll rect_W, ll rect_h = 0, ll rect_w = 0){ return (rect_h <= pos_x && pos_x < rect_H && rect_w <= pos_y && pos_y < rect_W); }
template<class T> vector<T> &operator++(vector<T> &v) {for(auto &e : v){e++;} return v;}
template<class T> vector<T> operator++(vector<T> &v, signed) {auto res=v; for(auto &e : v){e++;} return res;}
template<class T> vector<T> &operator--(vector<T> &v) {for(auto &e : v){e--;} return v;}
template<class T> vector<T> operator--(vector<T> &v, signed) {auto res=v; for(auto &e : v){e--;} return res;}
template<class T> vector<T> operator+(const vector<T> &x, const vector<T> &y) { assert(x.size() == y.size()); vector<T> ret(x.size()); for(int i = 0; i < (int)x.size(); i++) {ret[i] = x[i] + y[i];} return ret; }
template<class T> vector<T> operator-(const vector<T> &x, const vector<T> &y) { assert(x.size() == y.size()); vector<T> ret(x.size()); for(int i = 0; i < (int)x.size(); i++) {ret[i] = x[i] - y[i];} return ret; }
template<class T, class U> pair<T, U> operator+(const pair<T, U> &x, const pair<T, U> &y) { return make_pair(x.first + y.first, x.second + y.second); }
template<class T, class U> pair<T, U> operator-(const pair<T, U> &x, const pair<T, U> &y) { return make_pair(x.first - y.first, x.second - y.second); }
template<class T, class U> void operator+=(pair<T, U> &x, pair<T, U> &y) { x = x + y; }
template<class T, class U> void operator-=(pair<T, U> &x, pair<T, U> &y) { x = x - y; }
template<class T> size_t HashCombine(const size_t seed,const T &v){ return seed^(std::hash<T>()(v)+0x9e3779b9+(seed<<6)+(seed>>2)); }
template<class T,class S> struct std::hash<std::pair<T,S>>{ size_t operator()(const std::pair<T,S> &keyval) const noexcept { return HashCombine(std::hash<T>()(keyval.first), keyval.second); } };
template<class T> struct std::hash<std::vector<T>>{ size_t operator()(const std::vector<T> &keyval) const noexcept { size_t s=0; for (auto&& v: keyval) s=HashCombine(s,v); return s; } };
template<int N> struct HashTupleCore{ template<class Tuple> size_t operator()(const Tuple &keyval) const noexcept{ size_t s=HashTupleCore<N-1>()(keyval); return HashCombine(s,std::get<N-1>(keyval)); } };
template <> struct HashTupleCore<0>{ template<class Tuple> size_t operator()(const Tuple &keyval) const noexcept{ return 0; } };
template<class... Args> struct std::hash<std::tuple<Args...>>{ size_t operator()(const tuple<Args...> &keyval) const noexcept { return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval); } };
int main()
{
std::cin.tie(nullptr), std::ios_base::sync_with_stdio(false);
readll(X, Y, Z);
bool rev = X > Y;
if(X > Y) swap(X, Y);
if(Y == 0)
{
if(Z == 0)
{
out(3);
out(0, 0, 0);
return 0;
}
else
{
out(4);
out(0, Z, Z, 0);
return 0;
}
}
if(X == 0)
{
if(Y == Z)
{
out(3);
vll ans = {0, Y, Y};
if(rev) reverse(All(ans));
out(ans);
return 0;
}
else if(Z == 0)
{
out(5);
vll ans = {0, Y, Y, 0, Y};
if(rev) reverse(All(ans));
out(ans);
return 0;
}
}
vector<pair<__int128_t, __int128_t>> B = {{1, 0}, {0, 1}};
auto canda = [&](pair<__int128_t, __int128_t> p, __int128_t num)
{
auto [a, b] = p;
if(b == 0)
{
if(a*X == num) return (__int128_t)-2LL;
else return (__int128_t)-1LL;
}
else if(b > 0)
{
if(num - a*X >= 0 && (num - a*X) % b == 0) return (num - a*X)/b;
else return (__int128_t)-1LL;
}
else
{
if(a*X - num >= 0 && (a*X - num) % (-b) == 0) return (a*X - num)/(-b);
else return (__int128_t)-1LL;
}
};
ll mxL = 170;
vector<__int128_t> ans;
rep(k, mxL - 2)
{
auto A = B;
while(A.size() < mxL) A.push_back(A[A.size() - 2] + A.back());
vector<pair<__int128_t, __int128_t>> rA(mxL, {0, 1e12});
REP(i, 2, mxL - 1)
{
rA[i] = rA[i - 1];
auto [a, b] = A[i];
if(b == 0)
{
if(a >= 0) continue;
else rA[i] = {1e12, 0};
}
else if(b > 0)
{
if(a > 0) continue;
else chmax(rA[i].first, ((-a) * X + b - 1)/b);
}
else
{
if(a < 0)
{
rA[i] = {1e12, 0};
}
else chmin(rA[i].second, (a * X)/(-b));
}
}
bool fin = false;
REP(i, 1, mxL - 2)
{
if(fin) break;
REP(j, i + 1, mxL - 1)
{
auto za = canda(A[i], Z);
auto ya = canda(A[j], Y);
if(za == -2 && ya == -2)
{
za = rA[j].first;
ya = za;
}
else if(za == -2)
{
za = ya;
}
else if(ya == -2)
{
ya = za;
}
if(za == ya && max(rA[i].first, rA[j].first) <= za && za <= min(rA[i].second, rA[j].second))
{
vector<__int128_t> tmp;
REP(x, 0, j) tmp.push_back(A[x].first*X + A[x].second*za);
if(ans.empty() || ans.size() > tmp.size())
{
ans.swap(tmp);
}
fin = true;
break;
}
}
}
B.push_back(B[B.size() - 2] - B.back());
}
if(ans.empty()) out(-1);
else
{
if(rev) reverse(All(ans));
out(ans.size());
out(ans);
}
}