結果
| 問題 |
No.3162 Five Two Three
|
| ユーザー |
 kencho
|
| 提出日時 | 2025-05-05 00:34:58 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,897 bytes |
| コンパイル時間 | 2,537 ms |
| コンパイル使用メモリ | 214,228 KB |
| 実行使用メモリ | 37,248 KB |
| 最終ジャッジ日時 | 2025-05-05 01:36:33 |
| 合計ジャッジ時間 | 5,672 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 WA * 1 TLE * 1 |
| other | -- * 187 |
ソースコード
/*
shortest sequence A of non-negative integers ( |A| ≥ 3 )
─────────────────────────────────────────────────────────
|A_{i-1} – A_{i+1}| = A_i (i = 2 … |A|-1)
A_1 = X , A_|A| = Y , some A_j = Z
X , Y , Z ≤ 1 000 000 000 000
─────────────────────────────────────────────────────────
bidirectional breadth / iterative-deepening
state : a pair (pre , cur)
step : (pre , cur) → (cur , pre±cur)
depth : at most 90 (because every “−” step strictly decreases
the maximum of the two numbers, and they
never become negative)
meet in the middle
left : from (dummy , X)
right : from (Y , dummy)
dummy = 1 if the real endpoint is 0 (otherwise 0)
─> avoids the ‘(0 , 0) → (0 , 0)’ dead loop
to join the two frontiers we need pairs
(p , q) on the left
(q , r) on the right with |p – r| = q
r is therefore either p+q or |p−q|
path reconstruction
every node stores its parent key, depth and whether Z has already
appeared; when the two sides meet we can walk back to the roots
and build the whole sequence in O(|A|).
the whole search stays below a few 10⁵ states in practice and runs
comfortably within the limits.
*/
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;
const int64 LIM = 1'000'000'000'000LL;
/* ------------------------------------------------------------------ */
static inline i128 key(int64 a, int64 b) { // pack the pair into 128 bit
return (i128(a) << 64) | (uint64_t)b;
}
struct Node {
int64 pre, cur; // the pair itself
i128 par; // parent key (-1 == root)
uint8_t depth; // depth from its own root
bool hasZ; // did Z appear up to here?
};
/* ------------------------------------------------------------------ */
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int64 X, Y, Z;
if (!(cin >> X >> Y >> Z)) return 0;
/* length-3 ? ---------------------------------------------------- */
if (std::llabs(X - Y) == Z) {
cout << 3 << '\n' << X << ' ' << Z << ' ' << Y << '\n';
return 0;
}
/* bidirectional iterative deepening ----------------------------- */
const int MAXD = 90; // always enough for 0 … 10¹²
for (int D = 4; D <= MAXD; ++D) {
int Llim = D / 2, Rlim = D - Llim; // depth limits (inclusive)
unordered_map<i128, Node> L, R;
queue<i128> qL, qR;
auto newNode = [&](int64 a, int64 b, i128 par,
uint8_t d, bool z) -> Node {
return Node{a, b, par, d, z};
};
/* roots ----------------------------------------------------- */
int64 dummyL = (X == 0 ? 1 : 0);
int64 dummyR = (Y == 0 ? 1 : 0);
Node rootL = newNode(dummyL, X, -1, 0, (dummyL == Z) || (X == Z));
Node rootR = newNode(Y, dummyR, -1, 0, (Y == Z) || (dummyR == Z));
i128 kL = key(dummyL, X), kR = key(Y, dummyR);
L.emplace(kL, rootL); qL.push(kL);
R.emplace(kR, rootR); qR.push(kR);
/* ------------------------------------------------------------------
expand one side up to <limit> layers (breadth-first)
------------------------------------------------------------------ */
auto expand = [&](queue<i128>& Q,
unordered_map<i128, Node>& mp,
int limit) {
while (!Q.empty()) {
i128 k = Q.front(); Q.pop();
const Node nd = mp[k];
if (nd.depth >= limit) continue;
int64 a = nd.pre, b = nd.cur;
int64 nxt[2] = {a + b, std::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,
newNode(b, c, k,
nd.depth + 1,
nd.hasZ || (c == Z)));
Q.push(nk);
}
}
};
expand(qL, L, Llim);
expand(qR, R, Rlim);
/* meet-point search ----------------------------------------- */
for (const auto& kv : L) {
const Node& ln = kv.second;
int64 p = ln.pre, q = ln.cur;
/* candidates for r (because |p – r| must equal q) */
int64 cand[2] = {std::llabs(p - q), p + q};
for (int t = 0; t < 2; ++t) {
int64 r = cand[t];
if (r < 0 || r > LIM) continue;
auto it = R.find(key(q, r));
if (it == R.end()) continue;
const Node& rn = it->second;
if (!(ln.hasZ || rn.hasZ || q == Z || r == Z)) continue;
/* ------------------ path reconstruction ------------------ */
vector<int64> left; // X … q
for (i128 kk = kv.first; kk != -1; kk = L[kk].par)
left.push_back(L[kk].cur);
reverse(left.begin(), left.end());
/* right side : r , … , Y ------------------------------- */
vector<const Node*> chain; // meeting → root (right)
for (i128 kk = it->first; ; ) {
const Node* np = &R[kk];
chain.push_back(np);
if (np->par == -1) break;
kk = np->par;
}
vector<int64> right;
right.reserve(chain.size()); // r first
right.push_back(chain[0]->cur);
for (size_t i = 1; i < chain.size(); ++i)
right.push_back(chain[i]->pre); // then each ancestor's ‘pre’
/* concatenate & output --------------------------------- */
vector<int64> ans;
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';
return 0;
}