#include <bits/stdc++.h> using namespace std; constexpr int N = 3, MAXC = 1e5; void pour(int i, int j, const array<int, N>& s, array<int, N>& s_out, const array<int, N>& bsize) { if (s[i] + s[j] > bsize[j]) { s_out[i] -= bsize[j] - s[j]; s_out[j] = bsize[j]; } else { s_out[i] = 0; s_out[j] += s[i]; } } pair<char, int> construct(const array<int, N>& s, const array<int, N>& bsize) { if (s[0] == 0) { return {0, s[1]}; } else if (s[0] == bsize[0]) { return {1, s[1]}; } else if (s[1] == 0) { return {2, s[0]}; } else if (s[1] == bsize[1]) { return {3, s[0]}; } else if (s[2] == 0) { return {4, s[0]}; } else { return {5, s[0]}; } } void deconstruct(const char& c, const int& b, array<int, N>& s_out, const int& sum, const array<int, N>& bsize) { switch (c) { case 0: s_out[0] = 0; s_out[1] = b; s_out[2] = sum - b; break; case 1: s_out[0] = bsize[0]; s_out[1] = b; s_out[2] = sum - b - bsize[0]; break; case 2: s_out[0] = b; s_out[1] = 0; s_out[2] = sum - b; break; case 3: s_out[0] = b; s_out[1] = bsize[1]; s_out[2] = sum - b - bsize[1]; break; case 4: s_out[0] = b; s_out[1] = sum - b; s_out[2] = 0; break; case 5: s_out[0] = b; s_out[1] = sum - b - bsize[2]; s_out[2] = bsize[2]; break; } } namespace std { template<> struct hash<pair<char, int>> { size_t operator()(const pair<char, int>& p) const { return (int)p.first*(MAXC+1) + p.second; } }; } int main() { ios::sync_with_stdio(0); cin.tie(0); array<int, N> bottle_size, state; int sum = 0; for (auto& x : bottle_size) cin >> x; for (auto& x : state) { cin >> x; sum += x; } queue<pair<pair<char, int>, uint32_t>> Q; vector<char> vis(6*MAXC+10, 0); vector<uint32_t> dist(bottle_size.back()+1, UINT32_MAX); constexpr auto H = hash<pair<char, int>>(); for (auto& x : state) dist[x] = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i == j) continue; array<int, N> sp = state; pour(i, j, state, sp, bottle_size); for (auto& x : sp) dist[x] = min(dist[x], (uint32_t)1); auto p = construct(sp, bottle_size); vis[H(p)] = true; Q.push({p, 1}); } } while (not Q.empty()) { auto& [p, ops] = Q.front(); Q.pop(); array<int, N> s; deconstruct(p.first, p.second, s, sum, bottle_size); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i == j) continue; array<int, N> sp = s; pour(i, j, s, sp, bottle_size); const auto pp = construct(sp, bottle_size); auto& visited = vis[H(pp)]; if (not visited) { for (auto& x : sp) dist[x] = min(dist[x], ops+1); visited = true; Q.push({pp, ops+1}); } } } } for (auto& x : dist) cout << (int)x << ' '; }
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 115 116 117 118 119 120 121 122 123 124 125 | #include <bits/stdc++.h> using namespace std; constexpr int N = 3, MAXC = 1e5; void pour(int i, int j, const array<int, N>& s, array<int, N>& s_out, const array<int, N>& bsize) { if (s[i] + s[j] > bsize[j]) { s_out[i] -= bsize[j] - s[j]; s_out[j] = bsize[j]; } else { s_out[i] = 0; s_out[j] += s[i]; } } pair<char, int> construct(const array<int, N>& s, const array<int, N>& bsize) { if (s[0] == 0) { return {0, s[1]}; } else if (s[0] == bsize[0]) { return {1, s[1]}; } else if (s[1] == 0) { return {2, s[0]}; } else if (s[1] == bsize[1]) { return {3, s[0]}; } else if (s[2] == 0) { return {4, s[0]}; } else { return {5, s[0]}; } } void deconstruct(const char& c, const int& b, array<int, N>& s_out, const int& sum, const array<int, N>& bsize) { switch (c) { case 0: s_out[0] = 0; s_out[1] = b; s_out[2] = sum - b; break; case 1: s_out[0] = bsize[0]; s_out[1] = b; s_out[2] = sum - b - bsize[0]; break; case 2: s_out[0] = b; s_out[1] = 0; s_out[2] = sum - b; break; case 3: s_out[0] = b; s_out[1] = bsize[1]; s_out[2] = sum - b - bsize[1]; break; case 4: s_out[0] = b; s_out[1] = sum - b; s_out[2] = 0; break; case 5: s_out[0] = b; s_out[1] = sum - b - bsize[2]; s_out[2] = bsize[2]; break; } } namespace std { template<> struct hash<pair<char, int>> { size_t operator()(const pair<char, int>& p) const { return (int)p.first*(MAXC+1) + p.second; } }; } int main() { ios::sync_with_stdio(0); cin.tie(0); array<int, N> bottle_size, state; int sum = 0; for (auto& x : bottle_size) cin >> x; for (auto& x : state) { cin >> x; sum += x; } queue<pair<pair<char, int>, uint32_t>> Q; vector<char> vis(6*MAXC+10, 0); vector<uint32_t> dist(bottle_size.back()+1, UINT32_MAX); constexpr auto H = hash<pair<char, int>>(); for (auto& x : state) dist[x] = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i == j) continue; array<int, N> sp = state; pour(i, j, state, sp, bottle_size); for (auto& x : sp) dist[x] = min(dist[x], (uint32_t)1); auto p = construct(sp, bottle_size); vis[H(p)] = true; Q.push({p, 1}); } } while (not Q.empty()) { auto& [p, ops] = Q.front(); Q.pop(); array<int, N> s; deconstruct(p.first, p.second, s, sum, bottle_size); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i == j) continue; array<int, N> sp = s; pour(i, j, s, sp, bottle_size); const auto pp = construct(sp, bottle_size); auto& visited = vis[H(pp)]; if (not visited) { for (auto& x : sp) dist[x] = min(dist[x], ops+1); visited = true; Q.push({pp, ops+1}); } } } } for (auto& x : dist) cout << (int)x << ' '; } |