#include <bits/stdc++.h> #ifndef ONLINE_JUDGE # pragma GCC diagnostic warning "-Wall" # pragma GCC diagnostic warning "-Wextra" # pragma GCC diagnostic warning "-Wformat=2" # pragma GCC diagnostic warning "-Wnull-dereference" # pragma GCC diagnostic warning "-Wduplicated-branches" # pragma GCC diagnostic warning "-Wduplicated-cond" # pragma GCC diagnostic warning "-Wfloat-equal" # pragma GCC diagnostic warning "-Wshadow" # pragma GCC diagnostic warning "-Wconversion" # pragma GCC diagnostic warning "-Wlogical-op" # pragma GCC diagnostic warning "-Wvector-operation-performance" # pragma GCC diagnostic warning "-Wdisabled-optimization" # pragma GCC diagnostic warning "-Wunsafe-loop-optimizations" # pragma GCC diagnostic warning "-Wdouble-promotion" #endif #define rangeof(c) (c).begin(), (c).end() using namespace std; using ubyte = unsigned char; using byte = unsigned char; using ushort = unsigned short; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; struct Node { int a, b, c; bool operator==(Node other) const { return a == other.a && b == other.b && c == other.c; } }; Node maxx; template<int idx> int& get(Node &node); template<> int& get<0>(Node &node) { return node.a; } template<> int& get<1>(Node &node) { return node.b; } template<> int& get<2>(Node &node) { return node.c; } template<int ai, int bi> Node przelej(Node node) { int &a = get<ai>(node), &b = get<bi>(node); int cnt = min(a, get<bi>(maxx) - b); a -= cnt; b += cnt; return node; } struct Haszowanko { size_t operator()(Node node) const { ull const mod = 100000000000000003; return ((node.a * 2137ull % mod * 2137ull % mod + node.b * 2137ull % mod) % mod + node.c) % mod; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); Node init; cin >> maxx.a >> maxx.b >> maxx.c; cin >> init.a >> init.b >> init.c; vector<int> results(maxx.c + 1, INT_MAX); unordered_set<Node, Haszowanko> visited; queue<pair<Node, int>> q; q.push({init, 0}); visited.insert(init); while(!q.empty()) { Node node = q.front().first; int dist = q.front().second; q.pop(); results[node.a] = min(results[node.a], dist); results[node.b] = min(results[node.b], dist); results[node.c] = min(results[node.c], dist); auto neighbor = [&](Node node) { if(visited.count(node)) return; visited.insert(node); q.push({node, dist + 1}); }; neighbor(przelej<0, 1>(node)); neighbor(przelej<0, 2>(node)); neighbor(przelej<1, 0>(node)); neighbor(przelej<1, 2>(node)); neighbor(przelej<2, 0>(node)); neighbor(przelej<2, 1>(node)); }; for(int i: results) { cout << (i != INT_MAX ? i : -1) << " "; } cout << "\n"; //cout << "visited count: " << visited.size() << "\n"; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include <bits/stdc++.h> #ifndef ONLINE_JUDGE # pragma GCC diagnostic warning "-Wall" # pragma GCC diagnostic warning "-Wextra" # pragma GCC diagnostic warning "-Wformat=2" # pragma GCC diagnostic warning "-Wnull-dereference" # pragma GCC diagnostic warning "-Wduplicated-branches" # pragma GCC diagnostic warning "-Wduplicated-cond" # pragma GCC diagnostic warning "-Wfloat-equal" # pragma GCC diagnostic warning "-Wshadow" # pragma GCC diagnostic warning "-Wconversion" # pragma GCC diagnostic warning "-Wlogical-op" # pragma GCC diagnostic warning "-Wvector-operation-performance" # pragma GCC diagnostic warning "-Wdisabled-optimization" # pragma GCC diagnostic warning "-Wunsafe-loop-optimizations" # pragma GCC diagnostic warning "-Wdouble-promotion" #endif #define rangeof(c) (c).begin(), (c).end() using namespace std; using ubyte = unsigned char; using byte = unsigned char; using ushort = unsigned short; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; struct Node { int a, b, c; bool operator==(Node other) const { return a == other.a && b == other.b && c == other.c; } }; Node maxx; template<int idx> int& get(Node &node); template<> int& get<0>(Node &node) { return node.a; } template<> int& get<1>(Node &node) { return node.b; } template<> int& get<2>(Node &node) { return node.c; } template<int ai, int bi> Node przelej(Node node) { int &a = get<ai>(node), &b = get<bi>(node); int cnt = min(a, get<bi>(maxx) - b); a -= cnt; b += cnt; return node; } struct Haszowanko { size_t operator()(Node node) const { ull const mod = 100000000000000003; return ((node.a * 2137ull % mod * 2137ull % mod + node.b * 2137ull % mod) % mod + node.c) % mod; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); Node init; cin >> maxx.a >> maxx.b >> maxx.c; cin >> init.a >> init.b >> init.c; vector<int> results(maxx.c + 1, INT_MAX); unordered_set<Node, Haszowanko> visited; queue<pair<Node, int>> q; q.push({init, 0}); visited.insert(init); while(!q.empty()) { Node node = q.front().first; int dist = q.front().second; q.pop(); results[node.a] = min(results[node.a], dist); results[node.b] = min(results[node.b], dist); results[node.c] = min(results[node.c], dist); auto neighbor = [&](Node node) { if(visited.count(node)) return; visited.insert(node); q.push({node, dist + 1}); }; neighbor(przelej<0, 1>(node)); neighbor(przelej<0, 2>(node)); neighbor(przelej<1, 0>(node)); neighbor(przelej<1, 2>(node)); neighbor(przelej<2, 0>(node)); neighbor(przelej<2, 1>(node)); }; for(int i: results) { cout << (i != INT_MAX ? i : -1) << " "; } cout << "\n"; //cout << "visited count: " << visited.size() << "\n"; } |