量杯問題bitwise

/*

weak        weak  we      ak   we  akwea        weak  we
  weak    weak    we      ak   weak    weak    we  ak we
    weakweak      we      ak   wea       ak   we    akwe
      wea         we      ak   we        ak   we    akwe
      wea         we      ak   we        ak   we    akwe
      wea          eak  weak   we        ak    we  ak we
      wea            wea  ak   we        ak     weak  we
                                                      we
we      ak     wea  ak       weak                     we
 we    ak    wea  weak     wea  eak                   we
  we  ak    we      ak   wea      wea         we      we
   weak     we      ak   we        we         we      we
    we      we      ak   we        we         we      we
   we        wea  weak    wea    wea          weak  weak
weak           wea  akw      weak                weak


*/
using namespace std;
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <utility>
#include <bitset>
#include <set>
#include <string>
#include <stack>
#include <iomanip>
#include <map>
#include <memory.h>
#include <deque>

#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define LL long long
#define mid (LB+RB)/2
#define vvl vector <vector<LL>>
#define vl vector <LL>
#define mkp make_pair

//iterators
#define iter(x) x.begin(),x.end()
#define aiter(a,n) a,a+n

//loops
#define REP(n) for (int ___=n;___--;)
#define REP0(i,n) for (int i=0;i<n;++i)
#define REP1(i,n) for (int i=1;i<=n;++i)
#define FOR(i,b,l,k) for (int i=b;i!=l;i+=k)
#define forEach(i,v) for (auto i:v)

/*
yungyao so weeeeeeeeeeeeeeeeeeeeeeeeeeak
8e7 so dian
FHVirus so dian
youou so dian
KYW so dian
hubert so dian
jass so dian
tingyu so dian
panda so dian
*/

//IO
#include <iostream>
#define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);
//testing some stuff, still under construction
//a lot more useful while debug
inline void print(vector <int> v){
    for (auto i:v)
        cout << i << ' ';
    cout << '\n';
}
inline void print(vector <int> v,char sep,char end){
    for (auto i:v)
        cout << i << sep;
    cout << end;
}

//constants
#include <climits>
const LL maxn = 0,mod = 1e9 + 7;

//workspace

//gcd
int gcd(int x,int y){
    return x % y ? gcd(y,x%y) : y;
}

#include <unordered_set>
#include <unordered_map>

int n;
int H(int v[]){
    int ret = 0;
    REP0(i,n){
        ret = (ret << 6) | v[i];
    }
    return ret;
}

struct Node{
    int f;
    int method; //0 for emptying cup i, 1 for filling cup i, 2 for pouring cup i to j
    int i,j;
};

unordered_map <int,Node> father;
#include <fstream>

inline void solve(){
    int t;
    unordered_set <int> vis;
    ofstream fout;
    fout.open("papabeard.txt");

    cin >> n;
    int l[5];
    REP0(i,n) cin >> l[i];
    cin >> t;
    fout << "由" << n << "個量杯，容量分別為";
    REP0(i,n) fout << l[i] << (i != n-1 ? ", " : "，");
    fout << "量出" << t << "單位的水\n";

    queue <pii> bfs;
    bfs.push(mkp(0,0));

    int g = l[0],mx = l[0];
    for (int i=1;i<n;++i) {mx = max(mx,l[i]);g = gcd(g,l[i]);}
    if (t > mx || t % g){
        fout << "不存在方式可以量出t單位的水\n";
        return;
    }

    int end;
    while (bfs.size()){
        auto [h,d] = bfs.front(); bfs.pop();
        int v[5],v_copy[5];
        int h_c = h;
        for (int i=n;i--;){
            v[i] = h_c & ((1 << 6) - 1);
            h_c >>= 6;
            if (v[i] == t){
                stack <Node> sk;
                while (h){
                    sk.push(father[h]);
                    h = father[h].f;
                }
                fout << "共需" << d << "步\n";
                for (int s=1;sk.size();sk.pop(),++s){
                    auto [fr,m,i,j] = sk.top();
                    fout << "第" << s << "步：";
                    if (!m){
                        fout << "清空量杯" << i+1 << '\n';
                    }
                    else if (m == 1){
                        fout << "裝滿量杯" << i+1 << '\n';
                    }
                    else{
                        fout << "將量杯" << i+1 << "的水倒入量杯" << j+1 << '\n';
                    }
                }
                return;
            }
        }

        for (int i=0;i<n;++i){
            for (int j=0;j<n;++j){
                if (i == j){
                    if (v[i]){
                        REP0(k,n) v_copy[k] = v[k];
                        v_copy[i] = 0;
                        auto h_c = H(v_copy);
                        if (vis.find(h_c) == vis.end()){
                            bfs.push(mkp(h_c,d+1));
                            vis.insert(h_c);
                            father[h_c] = {h,0,i,-1};
                        }
                    }
                    if (v[i] != l[i]){
                        REP0(k,n) v_copy[k] = v[k];
                        v_copy[i] = l[i];
                        auto h_c = H(v_copy);
                        if (vis.find(h_c) == vis.end()){
                            bfs.push(mkp(h_c,d+1));
                            vis.insert(h_c);
                            father[h_c] = {h,1,i,-1};
                        }
                    }
                }
                else{
                    REP0(k,n) v_copy[k] = v[k];
                    if (v[i] + v[j] <= l[j]){
                        v_copy[i] = 0;
                        v_copy[j] = v[i] + v[j];
                    }
                    else{
                        v_copy[i] = v[i] + v[j] - l[j];
                        v_copy[j] = l[j];
                    }

                    auto h_c = H(v_copy);
                    if (vis.find(h_c) == vis.end()){
                        bfs.push(mkp(h_c,d+1));
                        vis.insert(h_c);
                        father[h_c] = {h,2,i,j};
                    }
                }
            }
        }
    }
}

signed main(){
    //theyRSOOOOOOOOODIAN
    //for (int ;cin;)//use in multi-testcases and end in EOF problems
    //int t,i=1;for (cin >> t;i<=t;++i)//use in multi-testcases problems
    //cout << "Case #" << i << ": ",//use in Google, FB competitions
    solve();//always used
    return 0;
}