結果
| 問題 | No.1152 10億ゲーム |
| ユーザー |
 tokusakurai
|
| 提出日時 | 2022-08-03 11:11:33 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 93 ms / 2,000 ms |
| コード長 | 5,841 bytes |
| コンパイル時間 | 2,267 ms |
| コンパイル使用メモリ | 208,096 KB |
| 最終ジャッジ日時 | 2025-01-30 17:18:38 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < n; i++)#define rep2(i, x, n) for (int i = x; i <= n; i++)#define rep3(i, x, n) for (int i = x; i >= n; i--)#define each(e, v) for (auto &e : v)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;template <typename T>bool chmax(T &x, const T &y) {return (x < y) ? (x = y, true) : false;}template <typename T>bool chmin(T &x, const T &y) {return (x > y) ? (x = y, true) : false;}template <typename T>int flg(T x, int i) {return (x >> i) & 1;}template <typename T>void print(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');if (v.empty()) cout << '\n';}template <typename T>void printn(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << '\n';}template <typename T>int lb(const vector<T> &v, T x) {return lower_bound(begin(v), end(v), x) - begin(v);}template <typename T>int ub(const vector<T> &v, T x) {return upper_bound(begin(v), end(v), x) - begin(v);}template <typename T>void rearrange(vector<T> &v) {sort(begin(v), end(v));v.erase(unique(begin(v), end(v)), end(v));}template <typename T>vector<int> id_sort(const vector<T> &v, bool greater = false) {int n = v.size();vector<int> ret(n);iota(begin(ret), end(ret), 0);sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });return ret;}template <typename S, typename T>pair<S, T> operator+(const pair<S, T> &p, const pair<S, T> &q) {return make_pair(p.first + q.first, p.second + q.second);}template <typename S, typename T>pair<S, T> operator-(const pair<S, T> &p, const pair<S, T> &q) {return make_pair(p.first - q.first, p.second - q.second);}template <typename S, typename T>istream &operator>>(istream &is, pair<S, T> &p) {S a;T b;is >> a >> b;p = make_pair(a, b);return is;}template <typename S, typename T>ostream &operator<<(ostream &os, const pair<S, T> &p) {return os << p.first << ' ' << p.second;}const int inf = (1 << 30) - 1;const ll INF = (1LL << 60) - 1;const int MOD = 1000000007;// const int MOD = 998244353;int calc(int i, int K) {int ret = 0;if (i > 0) ret++;if (i < K - 1) ret++;return ret;}pii calc_pair(int x) {int i = 0, j = 0;while (x % 2 == 0) {x /= 2;i++;}while (x % 5 == 0) {x /= 5;j++;}return make_pair(i, j);}int calc_int(int i, int j) {int x = 1;rep(k, i) x *= 2;rep(k, j) x *= 5;return x;}int main() {int K = 10;int dp[K][K][K][K][2];int deg[K][K][K][K];pii nxt[K][K][K][K];rep(i, K) rep(j, K) rep(k, K) rep(l, K) {dp[i][j][k][l][0] = inf;dp[i][j][k][l][1] = -inf;}rep(i, K) rep(j, K) rep(k, K) rep(l, K) {deg[i][j][k][l] = calc(k, K) + calc(l, K);if (k == K - 3 && l == K - 1) deg[i][j][k][l]++;}queue<tuple<int, int, int, int, int>> que;rep(i, K) rep(j, K) rep(m, 2) {dp[i][j][i][j][m] = 0;que.emplace(i, j, i, j, m);}while (!empty(que)) {auto [i, j, k, l, m] = que.front();que.pop();int d = dp[i][j][k][l][m];rep2(x, -1, 1) rep2(y, -1, 1) {if (abs(x + y) != 1) continue;if (m == 0) {int nk = k + x, nl = l + y;if (nk < 0 || nk >= K || nl < 0 || nl >= K) continue;if (dp[i][j][nk][nl][1] != -inf) continue;if (--deg[i][j][nk][nl] == 0) {dp[i][j][nk][nl][1] = d + 1;que.emplace(i, j, nk, nl, 1);}} else {int ni = i + x, nj = j + y;if (ni < 0 || ni >= K || nj < 0 || nj >= K) continue;if (chmin(dp[ni][nj][k][l][0], d + 1)) {nxt[ni][nj][k][l] = make_pair(i, j);que.emplace(ni, nj, k, l, 0);}}}if (m == 0 && k == K - 1 && l == K - 1) {int nk = K - 3, nl = K - 1;if (nk < 0 || nk >= K || nl < 0 || nl >= K) continue;if (dp[i][j][nk][nl][1] != -inf) continue;if (--deg[i][j][nk][nl] == 0) {dp[i][j][nk][nl][1] = d + 1;que.emplace(i, j, nk, nl, 1);}}if (m == 1 && i == K - 1 && j == K - 1) {int ni = K - 3, nj = K - 1;if (ni < 0 || ni >= K || nj < 0 || nj >= K) continue;if (chmin(dp[ni][nj][k][l][0], d + 1)) {nxt[ni][nj][k][l] = make_pair(i, j);que.emplace(ni, nj, k, l, 0);}}}// int mi = inf, ma = -inf;// rep(i, K) rep(j, K) rep(k, K) rep(l, K) rep(m, 2) {// chmin(mi, dp[i][j][k][l][m]);// chmax(ma, dp[i][j][k][l][m]);// }// cout << mi << ' ' << ma << '\n';int s, t;cin >> s >> t;auto [si, sj] = calc_pair(s);auto [ti, tj] = calc_pair(t);// cout << si << ' ' << sj << ' ' << ti << ' ' << tj << '\n';while (true) {// cout << dp[si][sj][ti][tj][0] << '\n';auto [ni, nj] = nxt[si][sj][ti][tj];cout << calc_int(ni, nj) << '\n';swap(si, ni), swap(sj, nj);if (si == ti && sj == tj) break;int p;cin >> p;tie(ti, tj) = calc_pair(p);if (si == ti && sj == tj) break;}}