Submission #70299783

---

Source Code Expand

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>


#include <iostream>
#include <string>
#include <utility>
#include <vector>

class JsonDumper {
    struct KeyValue {
        std::string key;
        std::string value;
    };

    std::vector<KeyValue> _items;

    bool dump_at_end = false;

public:
    JsonDumper(bool dump_at_end_ = false) : dump_at_end(dump_at_end_) {}

    ~JsonDumper() {
        if (dump_at_end) std::cout << dump() << std::endl;
    }

    void set_dump_at_end() { dump_at_end = true; }

    void operator()(const std::string &key, const std::string &value) {
        _items.push_back(KeyValue{key, "\"" + value + "\""});
    }

    template <class T> void operator()(const std::string &key, T value) {
        _items.push_back(KeyValue{key, std::to_string(value)});
    }

    std::string dump() const {
        std::string ret = "{\n";

        if (!_items.empty()) {
            for (const auto &[k, v] : _items) ret += "    \"" + k + "\": " + v + ",\n";

            ret.erase(ret.end() - 2);
        }

        ret += "}";
        return ret;
    }
} jdump;

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end) - 1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }

int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); }
template <class T1, class T2> T1 floor_div(T1 num, T2 den) {
    return (num > 0 ? num / den : -((-num + den - 1) / den));
}
template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) {
    return std::make_pair(l.first + r.first, l.second + r.second);
}
template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) {
    return std::make_pair(l.first - r.first, l.second - r.second);
}
template <class T> std::vector<T> sort_unique(std::vector<T> vec) {
    sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}
template <class T> int arglb(const std::vector<T> &v, const T &x) {
    return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x));
}
template <class T> int argub(const std::vector<T> &v, const T &x) {
    return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x));
}
template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) {
    for (auto &v : vec) is >> v;
    return is;
}

template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec);
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr);
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec);
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec);
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp);
template <class OStream, class TK, class TV, class TH>
OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp);
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl);

template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) {
    os << '[';
    for (auto v : vec) os << v << ',';
    os << ']';
    return os;
}
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) {
    os << '[';
    for (auto v : arr) os << v << ',';
    os << ']';
    return os;
}
template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) {
    std::apply([&is](auto &&...args) { ((is >> args), ...); }, tpl);
    return is;
}
template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) {
    os << '(';
    std::apply([&os](auto &&...args) { ((os << args << ','), ...); }, tpl);
    return os << ')';
}
template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) {
    os << '{';
    for (auto v : vec) os << v << ',';
    os << '}';
    return os;
}
template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) {
    os << "deq[";
    for (auto v : vec) os << v << ',';
    os << ']';
    return os;
}
template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) {
    os << '{';
    for (auto v : vec) os << v << ',';
    os << '}';
    return os;
}
template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) {
    os << '{';
    for (auto v : vec) os << v << ',';
    os << '}';
    return os;
}
template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) {
    os << '{';
    for (auto v : vec) os << v << ',';
    os << '}';
    return os;
}
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) {
    return os << '(' << pa.first << ',' << pa.second << ')';
}
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) {
    os << '{';
    for (auto v : mp) os << v.first << "=>" << v.second << ',';
    os << '}';
    return os;
}
template <class OStream, class TK, class TV, class TH>
OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) {
    os << '{';
    for (auto v : mp) os << v.first << "=>" << v.second << ',';
    os << '}';
    return os;
}

#ifdef HITONANODE_LOCAL
const std::string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m",
                  BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m",
                  NORMAL_FAINT = "\033[0;2m";
#define dbg(x)                                                                                                        \
    std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") "        \
              << __FILE__ << COLOR_RESET << std::endl
#define dbgif(cond, x)                                                                                                \
    ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__      \
                        << ") " << __FILE__ << COLOR_RESET << std::endl                                               \
            : std::cerr)
#else
#define dbg(x) 0
#define dbgif(cond, x) 0
#endif

#ifdef BENCHMARK
#define dump_onlinejudge(x) 0
struct setenv {
    setenv() { jdump.set_dump_at_end(); }
} setenv_;
#else
#define dump_onlinejudge(x) (std::cout << (x) << std::endl)
#endif

#include <algorithm>
#include <chrono>
#include <iostream>
#include <limits>
#include <random>
#include <string>
#include <utility>
#include <vector>

using namespace std;

struct PlanDetail {
    vector<vector<int>> weapon_use;
    vector<int> bare_hand;
    int total_attacks;
};

struct ActionBuilder {
    const vector<int> &H;
    const vector<vector<int>> &A;

    ActionBuilder(const vector<int> &hardness, const vector<vector<int>> &damage) : H(hardness), A(damage) {}

    vector<pair<int, int>> build_actions(const vector<int> &order, const PlanDetail &plan) const {
        vector<pair<int, int>> actions;
        actions.reserve(plan.total_attacks);
        vector<int> hardness = H;
        int N = static_cast<int>(order.size());
        for (int idx = 0; idx < N; ++idx) {
            int chest = order[idx];
            for (int prev = 0; prev < idx; ++prev) {
                int weapon = order[prev];
                int cnt = plan.weapon_use[weapon][chest];
                for (int t = 0; t < cnt; ++t) {
                    if (hardness[chest] <= 0) break;
                    int dmg = min(A[weapon][chest], hardness[chest]);
                    if (dmg <= 0) break;
                    actions.emplace_back(weapon, chest);
                    hardness[chest] -= dmg;
                }
            }
            int bare = plan.bare_hand[chest];
            for (int t = 0; t < bare; ++t) {
                if (hardness[chest] <= 0) break;
                actions.emplace_back(-1, chest);
                hardness[chest] -= 1;
            }
            while (hardness[chest] > 0) {
                actions.emplace_back(-1, chest);
                hardness[chest] -= 1;
            }
        }
        return actions;
    }
};

struct Solver {
    int N;
    vector<int> H;
    vector<int> C;
    vector<vector<int>> A;
    mt19937_64 rng;

    struct GraphState {
        vector<vector<int>> use;
        vector<int> out_used;
    };

    struct StateEvaluation {
        bool valid = false;
        int score = 0;
        vector<int> order;
        vector<int> bare_hand;
    };

    struct Ver15State {
        vector<int> order;
        GraphState graph;
        vector<int> pos;
        vector<long long> contribution;
        vector<int> bare_hand;
        long long score = (1LL << 60);
        bool valid = false;
    };

    Solver() : rng(20241003ULL) {} // 固定 seed で再現性を確保

    void read_input() {
        cin >> N;
        H.assign(N, 0);
        C.assign(N, 0);
        for (int i = 0; i < N; ++i) { cin >> H[i]; }
        for (int i = 0; i < N; ++i) { cin >> C[i]; }
        A.assign(N, vector<int>(N, 0));
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) { cin >> A[i][j]; }
        }
    }

    int evaluate(const vector<int> &order) const {
        vector<int> remaining(H.begin(), H.end());
        int weapon_uses = 0;
        for (int pos = N - 1; pos >= 0; --pos) {
            int weapon = order[pos];
            int limit = C[weapon];
            for (int iter = 0; iter < limit; ++iter) {
                int best_chest = -1;
                int best_value = 1;
                for (int nxt = pos + 1; nxt < N; ++nxt) {
                    int chest = order[nxt];
                    if (remaining[chest] <= 0) continue;
                    int val = remaining[chest];
                    int dmg = A[weapon][chest];
                    if (dmg < val) val = dmg;
                    if (val > best_value) {
                        best_value = val;
                        best_chest = chest;
                    }
                }
                if (best_chest == -1) break;
                int dmg = min(A[weapon][best_chest], remaining[best_chest]);
                if (dmg <= 1) break;
                remaining[best_chest] -= dmg;
                ++weapon_uses;
            }
        }
        long long total = weapon_uses;
        for (int chest = 0; chest < N; ++chest) {
            if (remaining[chest] > 0) { total += remaining[chest]; }
        }
        return static_cast<int>(total);
    }

    PlanDetail build_plan(const vector<int> &order) const {
        PlanDetail plan;
        plan.weapon_use.assign(N, vector<int>(N, 0));
        plan.bare_hand.assign(N, 0);
        vector<int> remaining(H.begin(), H.end());
        int weapon_uses = 0;
        for (int pos = N - 1; pos >= 0; --pos) {
            int weapon = order[pos];
            int limit = C[weapon];
            for (int iter = 0; iter < limit; ++iter) {
                int best_chest = -1;
                int best_value = 1;
                for (int nxt = pos + 1; nxt < N; ++nxt) {
                    int chest = order[nxt];
                    if (remaining[chest] <= 0) continue;
                    int val = remaining[chest];
                    int dmg = A[weapon][chest];
                    if (dmg < val) val = dmg;
                    if (val > best_value) {
                        best_value = val;
                        best_chest = chest;
                    }
                }
                if (best_chest == -1) break;
                int dmg = min(A[weapon][best_chest], remaining[best_chest]);
                if (dmg <= 1) break;
                remaining[best_chest] -= dmg;
                plan.weapon_use[weapon][best_chest] += 1;
                ++weapon_uses;
            }
        }
        long long total = weapon_uses;
        for (int chest = 0; chest < N; ++chest) {
            if (remaining[chest] > 0) {
                plan.bare_hand[chest] = remaining[chest];
                total += remaining[chest];
            }
        }
        plan.total_attacks = static_cast<int>(total);
        return plan;
    }

    GraphState state_from_plan(const PlanDetail &plan) const {
        GraphState state;
        state.use = plan.weapon_use;
        state.out_used.assign(N, 0);
        for (int i = 0; i < N; ++i) {
            int sum = 0;
            for (int j = 0; j < N; ++j) { sum += state.use[i][j]; }
            state.out_used[i] = sum;
        }
        return state;
    }

    bool recompute_ver15_state(Ver15State &st) const {
        st.pos.assign(N, -1);
        for (int idx = 0; idx < N; ++idx) {
            int chest = st.order[idx];
            st.pos[chest] = idx;
        }
        st.graph.out_used.assign(N, 0);
        st.contribution.assign(N, 0);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                int cnt = st.graph.use[i][j];
                if (cnt == 0) continue;
                if (st.pos[i] >= st.pos[j]) {
                    st.valid = false;
                    return false;
                }
                st.graph.out_used[i] += cnt;
                if (st.graph.out_used[i] > C[i]) {
                    st.valid = false;
                    return false;
                }
                st.contribution[j] += 1LL * cnt * A[i][j];
            }
        }
        st.bare_hand.assign(N, 0);
        long long total = 0;
        for (int i = 0; i < N; ++i) { total += st.graph.out_used[i]; }
        for (int i = 0; i < N; ++i) {
            long long need = static_cast<long long>(H[i]) - st.contribution[i];
            if (need > 0) {
                st.bare_hand[i] = static_cast<int>(need);
                total += need;
            }
        }
        st.score = total;
        st.valid = true;
        return true;
    }

    Ver15State build_ver15_state(const vector<int> &order, const PlanDetail &plan) const {
        Ver15State st;
        st.order = order;
        st.graph.use = plan.weapon_use;
        st.graph.out_used.assign(N, 0);
        for (int i = 0; i < N; ++i) {
            int sum = 0;
            for (int j = 0; j < N; ++j) { sum += st.graph.use[i][j]; }
            st.graph.out_used[i] = sum;
        }
        if (!recompute_ver15_state(st)) { st.valid = false; }
        return st;
    }

    vector<long long> compute_contribution(const GraphState &state) const {
        vector<long long> contribution(N, 0);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (state.use[i][j] == 0) continue;
                contribution[j] += 1LL * state.use[i][j] * A[i][j];
            }
        }
        return contribution;
    }

    bool has_path(const GraphState &state, int src, int dst) const {
        if (src == dst) return true;
        vector<int> visited(N, 0);
        vector<int> stack;
        stack.reserve(N);
        stack.push_back(src);
        visited[src] = 1;
        while (!stack.empty()) {
            int v = stack.back();
            stack.pop_back();
            for (int to = 0; to < N; ++to) {
                if (state.use[v][to] == 0) continue;
                if (to == dst) return true;
                if (!visited[to]) {
                    visited[to] = 1;
                    stack.push_back(to);
                }
            }
        }
        return false;
    }

    bool would_create_cycle(const GraphState &state, int from, int to) const {
        if (from == to) return true;
        return has_path(state, to, from);
    }

    StateEvaluation evaluate_state(const GraphState &state) const {
        StateEvaluation eval;
        vector<int> indeg(N, 0);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (state.use[i][j] > 0) { indeg[j] += 1; }
            }
        }

        vector<int> order;
        order.reserve(N);
        vector<int> queue;
        queue.reserve(N);
        for (int i = 0; i < N; ++i) {
            if (indeg[i] == 0) queue.push_back(i);
        }
        for (size_t qi = 0; qi < queue.size(); ++qi) {
            int v = queue[qi];
            order.push_back(v);
            for (int to = 0; to < N; ++to) {
                if (state.use[v][to] > 0) {
                    if (--indeg[to] == 0) { queue.push_back(to); }
                }
            }
        }
        if (static_cast<int>(order.size()) != N) { return eval; }

        vector<long long> contribution = compute_contribution(state);
        vector<int> bare_hand(N, 0);
        long long total = 0;
        for (int i = 0; i < N; ++i) {
            if (state.out_used[i] > C[i]) { return eval; }
            total += state.out_used[i];
        }
        for (int i = 0; i < N; ++i) {
            long long need = static_cast<long long>(H[i]) - contribution[i];
            if (need > 0) {
                bare_hand[i] = static_cast<int>(need);
                total += need;
            }
        }
        eval.valid = true;
        eval.score = static_cast<int>(total);
        eval.order = std::move(order);
        eval.bare_hand = std::move(bare_hand);
        return eval;
    }

    void remove_redundant_edges(GraphState &state) const {
        vector<long long> contribution = compute_contribution(state);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                while (state.use[i][j] > 0 && contribution[j] - A[i][j] >= H[j]) {
                    state.use[i][j] -= 1;
                    state.out_used[i] -= 1;
                    contribution[j] -= A[i][j];
                }
            }
        }
    }

    bool apply_ver15_case_without_bare(Ver15State &st, int v) const {
        int old_pos = st.pos[v];
        vector<int> new_order = st.order;
        int last_donor_pos = -1;
        for (int w = 0; w < N; ++w) {
            if (st.graph.use[w][v] > 0) { last_donor_pos = max(last_donor_pos, st.pos[w]); }
        }
        int insert_pos = last_donor_pos + 1;
        new_order.erase(new_order.begin() + old_pos);
        if (insert_pos > old_pos) insert_pos--;
        if (insert_pos < 0) insert_pos = 0;
        if (insert_pos > static_cast<int>(new_order.size())) insert_pos = static_cast<int>(new_order.size());
        new_order.insert(new_order.begin() + insert_pos, v);
        st.order = std::move(new_order);

        for (int t = 0; t < N; ++t) { st.graph.use[v][t] = 0; }

        if (!recompute_ver15_state(st)) return false;

        vector<long long> contrib = st.contribution;
        int pos_v = st.pos[v];
        vector<int> targets;
        targets.reserve(N);
        for (int idx = pos_v + 1; idx < N; ++idx) {
            int chest = st.order[idx];
            if (contrib[chest] < H[chest]) { targets.push_back(chest); }
        }
        sort(targets.begin(), targets.end(), [&](int lhs, int rhs) {
            if (A[v][lhs] != A[v][rhs]) return A[v][lhs] > A[v][rhs];
            if (H[lhs] != H[rhs]) return H[lhs] < H[rhs];
            return lhs < rhs;
        });
        int remaining = C[v];
        for (int chest : targets) {
            if (remaining <= 0) break;
            int damage = A[v][chest];
            if (damage <= 0) continue;
            long long need = static_cast<long long>(H[chest]) - contrib[chest];
            if (need <= 0) continue;
            int add = static_cast<int>(min<long long>(remaining, (need + damage - 1) / damage));
            if (add <= 0) continue;
            st.graph.use[v][chest] += add;
            contrib[chest] += 1LL * add * damage;
            remaining -= add;
        }

        if (!recompute_ver15_state(st)) return false;
        return true;
    }

    bool apply_ver15_case_with_bare(Ver15State &st, int v) const {
        int old_pos = st.pos[v];
        vector<int> new_order = st.order;
        int last_target_pos = -1;
        for (int t = 0; t < N; ++t) {
            if (st.graph.use[v][t] > 0) { last_target_pos = max(last_target_pos, st.pos[t]); }
        }
        int insert_pos = (last_target_pos >= 0) ? last_target_pos : old_pos;
        new_order.erase(new_order.begin() + old_pos);
        if (insert_pos > old_pos) insert_pos--;
        if (insert_pos < 0) insert_pos = 0;
        if (insert_pos > static_cast<int>(new_order.size())) insert_pos = static_cast<int>(new_order.size());
        new_order.insert(new_order.begin() + insert_pos, v);
        st.order = std::move(new_order);

        st.pos.assign(N, -1);
        for (int idx = 0; idx < N; ++idx) { st.pos[st.order[idx]] = idx; }
        int pos_v = st.pos[v];
        for (int t = 0; t < N; ++t) {
            if (st.graph.use[v][t] > 0 && st.pos[t] <= pos_v) { st.graph.use[v][t] = 0; }
        }
        for (int w = 0; w < N; ++w) { st.graph.use[w][v] = 0; }

        if (!recompute_ver15_state(st)) return false;

        vector<long long> contrib = st.contribution;
        long long need = static_cast<long long>(H[v]) - contrib[v];
        if (need <= 0) { return true; }

        vector<int> candidates;
        candidates.reserve(pos_v);
        for (int idx = 0; idx < pos_v; ++idx) {
            int weapon = st.order[idx];
            if (A[weapon][v] <= 0) continue;
            if (st.graph.out_used[weapon] >= C[weapon]) continue;
            candidates.push_back(weapon);
        }
        sort(candidates.begin(), candidates.end(), [&](int lhs, int rhs) {
            if (A[lhs][v] != A[rhs][v]) return A[lhs][v] > A[rhs][v];
            if (C[lhs] != C[rhs]) return C[lhs] > C[rhs];
            return lhs < rhs;
        });

        vector<long long> contrib_local = contrib;
        for (int weapon : candidates) {
            if (need <= 0) break;
            int available = C[weapon] - st.graph.out_used[weapon];
            if (available <= 0) continue;
            int damage = A[weapon][v];
            if (damage <= 0) continue;
            long long required = (need + damage - 1) / damage;
            int add = static_cast<int>(min<long long>(available, required));
            if (add <= 0) continue;
            st.graph.use[weapon][v] += add;
            st.graph.out_used[weapon] += add;
            contrib_local[v] += 1LL * add * damage;
            need -= 1LL * add * damage;
        }

        if (!recompute_ver15_state(st)) return false;
        return true;
    }

    pair<vector<int>, PlanDetail>
    run_ver15_only(const vector<int> &order_v1, const PlanDetail &plan_v1, double time_limit_sec) {
        if (time_limit_sec <= 0.0) { return {order_v1, plan_v1}; }
        Ver15State current = build_ver15_state(order_v1, plan_v1);
        if (!current.valid) { return {order_v1, plan_v1}; }
        Ver15State best = current;

        uniform_int_distribution<int> idx_dist(0, N - 1);
        auto start_time = chrono::steady_clock::now();
        while (true) {
            auto now = chrono::steady_clock::now();
            double elapsed = chrono::duration<double>(now - start_time).count();
            if (elapsed > time_limit_sec) break;

            int v = idx_dist(rng);
            Ver15State candidate = current;
            bool success = false;
            if (current.bare_hand[v] == 0) {
                success = apply_ver15_case_without_bare(candidate, v);
            } else {
                success = apply_ver15_case_with_bare(candidate, v);
            }
            if (!success || !candidate.valid) continue;
            if (candidate.score < current.score) {
#ifdef HITONANODE_LOCAL
                long long prev_score = current.score;
                const char *op_name = (current.bare_hand[v] == 0) ? "ver1.5_after" : "ver1.5_before";
#endif
                current = candidate;
                if (candidate.score < best.score) { best = candidate; }
            }
        }

        PlanDetail base_plan = plan_v1;
        if (best.valid && best.score < plan_v1.total_attacks) {
            PlanDetail result_plan;
            result_plan.weapon_use = best.graph.use;
            result_plan.bare_hand = best.bare_hand;
            result_plan.total_attacks = static_cast<int>(best.score);
            return {best.order, std::move(result_plan)};
        }
        return {order_v1, base_plan};
    }

    GraphState improve_state(GraphState initial_state, double time_limit_sec, StateEvaluation &best_eval_out) {
        constexpr int DAMAGE_THRESHOLD = 5;
        GraphState current = std::move(initial_state);
        StateEvaluation current_eval = evaluate_state(current);
        GraphState best_state = current;
        StateEvaluation best_eval = current_eval;

        uniform_int_distribution<int> idx_dist(0, N - 1);

        auto start_time = chrono::steady_clock::now();
        while (true) {
            auto now = chrono::steady_clock::now();
            double elapsed = chrono::duration<double>(now - start_time).count();
            if (elapsed > time_limit_sec) break;

            GraphState candidate = current;
            vector<long long> contribution = compute_contribution(candidate);
            int pivot = idx_dist(rng);

            for (int j = 0; j < N; ++j) {
                if (candidate.use[j][pivot] > 0) {
                    candidate.out_used[j] -= candidate.use[j][pivot];
                    contribution[pivot] -= 1LL * candidate.use[j][pivot] * A[j][pivot];
                    candidate.use[j][pivot] = 0;
                }
            }
            for (int k = 0; k < N; ++k) {
                if (candidate.use[pivot][k] > 0) {
                    candidate.out_used[pivot] -= candidate.use[pivot][k];
                    contribution[k] -= 1LL * candidate.use[pivot][k] * A[pivot][k];
                    candidate.use[pivot][k] = 0;
                }
            }

            vector<int> donors;
            donors.reserve(N);
            for (int j = 0; j < N; ++j) {
                if (j == pivot) continue;
                if (A[j][pivot] <= DAMAGE_THRESHOLD) continue;
                if (candidate.out_used[j] >= C[j]) continue;
                donors.push_back(j);
            }
            sort(donors.begin(), donors.end(), [&](int lhs, int rhs) {
                if (A[lhs][pivot] != A[rhs][pivot]) { return A[lhs][pivot] > A[rhs][pivot]; }
                return H[lhs] < H[rhs];
            });
            long long remaining = static_cast<long long>(H[pivot]) - contribution[pivot];
            for (int donor : donors) {
                if (remaining <= 0) break;
                int available = C[donor] - candidate.out_used[donor];
                if (available <= 0) continue;
                int damage = A[donor][pivot];
                long long need = remaining > 0 ? remaining : 0;
                long long use_count = min<long long>(available, (need + damage - 1) / damage);
                if (use_count <= 0) continue;
                candidate.use[donor][pivot] += static_cast<int>(use_count);
                candidate.out_used[donor] += static_cast<int>(use_count);
                contribution[pivot] += use_count * damage;
                remaining = static_cast<long long>(H[pivot]) - contribution[pivot];
            }

            vector<int> targets;
            targets.reserve(N);
            for (int k = 0; k < N; ++k) {
                if (k == pivot) continue;
                if (A[pivot][k] <= DAMAGE_THRESHOLD) continue;
                targets.push_back(k);
            }
            sort(targets.begin(), targets.end(), [&](int lhs, int rhs) {
                if (A[pivot][lhs] != A[pivot][rhs]) { return A[pivot][lhs] > A[pivot][rhs]; }
                return H[lhs] < H[rhs];
            });
            for (int target : targets) {
                if (candidate.out_used[pivot] >= C[pivot]) break;
                if (would_create_cycle(candidate, pivot, target)) continue;
                long long need = static_cast<long long>(H[target]) - contribution[target];
                if (need <= 0) continue;
                int available = C[pivot] - candidate.out_used[pivot];
                if (available <= 0) break;
                int damage = A[pivot][target];
                long long use_count = min<long long>(available, (need + damage - 1) / damage);
                if (use_count <= 0) continue;
                candidate.use[pivot][target] += static_cast<int>(use_count);
                candidate.out_used[pivot] += static_cast<int>(use_count);
                contribution[target] += use_count * damage;
            }

            StateEvaluation cand_eval = evaluate_state(candidate);
            if (!cand_eval.valid) continue;
            if (current_eval.valid && cand_eval.score >= current_eval.score) continue;

            remove_redundant_edges(candidate);
            cand_eval = evaluate_state(candidate);
            if (!cand_eval.valid) continue;
            if (current_eval.valid && cand_eval.score >= current_eval.score) continue;

#ifdef HITONANODE_LOCAL
#endif
            current = std::move(candidate);
            current_eval = cand_eval;
            if (!best_eval.valid || cand_eval.score < best_eval.score) {
                best_state = current;
                best_eval = cand_eval;
            }
        }

        if (best_eval.valid && (!best_eval_out.valid || best_eval.score < best_eval_out.score)) {
            best_eval_out = best_eval;
        }
        return best_state;
    }

    pair<vector<int>, PlanDetail>
    run_ver2_only(const vector<int> &order_v1, const PlanDetail &plan_v1, double time_limit_sec) {
        PlanDetail base_plan = plan_v1;
        base_plan.total_attacks = plan_v1.total_attacks;
        if (time_limit_sec <= 0.0) { return {order_v1, base_plan}; }

        GraphState initial_state = state_from_plan(plan_v1);
        StateEvaluation initial_eval = evaluate_state(initial_state);
        if (!initial_eval.valid) { return {order_v1, base_plan}; }
        if (initial_eval.order.empty()) { initial_eval.order = order_v1; }

        StateEvaluation best_eval = initial_eval;
        GraphState best_state = initial_state;
        StateEvaluation eval_out = best_eval;
        GraphState improved = improve_state(initial_state, time_limit_sec, eval_out);
        if (eval_out.valid && (!best_eval.valid || eval_out.score < best_eval.score)) {
            best_state = std::move(improved);
            best_eval = eval_out;
        }

        if (!best_eval.valid || best_eval.score >= plan_v1.total_attacks) { return {order_v1, base_plan}; }

        PlanDetail result_plan;
        result_plan.weapon_use = best_state.use;
        result_plan.bare_hand = best_eval.bare_hand;
        result_plan.total_attacks = best_eval.score;
        return {best_eval.order, std::move(result_plan)};
    }

    vector<int> improve_order(vector<int> order, double time_limit_sec) {
        vector<int> current = order;
        int current_score = evaluate(current);
        vector<int> best = current;
        int best_score = current_score;

        uniform_int_distribution<int> op_dist(0, 2);
        uniform_int_distribution<int> idx_dist(0, N - 1);

        auto start_time = chrono::steady_clock::now();
        while (true) {
            auto now = chrono::steady_clock::now();
            double elapsed = chrono::duration<double>(now - start_time).count();
            if (elapsed > time_limit_sec) break;

            vector<int> candidate = current;
            int op = op_dist(rng) * 0 + 1;
            string op_name;
            if (op == 0) { // swap
                int i = idx_dist(rng);
                int j = idx_dist(rng);
                if (i == j) continue;
                swap(candidate[i], candidate[j]);
                op_name = "swap";
            } else if (op == 1) { // insert
                int i = idx_dist(rng);
                int j = idx_dist(rng);
                if (i == j) continue;
                int val = candidate[i];
                candidate.erase(candidate.begin() + i);
                candidate.insert(candidate.begin() + j, val);
                op_name = "insert";
            } else { // reverse segment
                int l = idx_dist(rng);
                int r = idx_dist(rng);
                if (l == r) continue;
                if (l > r) swap(l, r);
                reverse(candidate.begin() + l, candidate.begin() + r + 1);
                op_name = "reverse";
            }

            int cand_score = evaluate(candidate);
            if (cand_score < current_score) {
#ifdef HITONANODE_LOCAL
                int prev_score = current_score;
#endif
                current.swap(candidate);
                current_score = cand_score;
#ifdef HITONANODE_LOCAL
#endif
                if (cand_score < best_score) {
                    best = current;
                    best_score = cand_score;
                }
            }
        }
        return best;
    }

    void solve() {
        vector<int> initial_order(N);
        for (int i = 0; i < N; ++i) { initial_order[i] = i; }
        sort(initial_order.begin(), initial_order.end(), [&](int lhs, int rhs) {
            if (C[lhs] != C[rhs]) return C[lhs] > C[rhs];
            if (H[lhs] != H[rhs]) return H[lhs] < H[rhs];
            return lhs < rhs;
        });

        const double TOTAL_LIMIT = 1.8;
        const double VER1_LIMIT = 0.6;
        const double VER15_LIMIT = 0.6;
        double VER2_LIMIT = TOTAL_LIMIT - VER1_LIMIT - VER15_LIMIT;
        if (VER2_LIMIT < 0.0) VER2_LIMIT = 0.0;

        vector<int> best_order_v1 = improve_order(initial_order, VER1_LIMIT);
        PlanDetail best_plan_v1 = build_plan(best_order_v1);

        vector<int> current_order = best_order_v1;
        PlanDetail current_plan = best_plan_v1;

        auto ver15_result = run_ver15_only(current_order, current_plan, VER15_LIMIT);
        if (ver15_result.second.total_attacks < current_plan.total_attacks) {
            current_order = ver15_result.first;
            current_plan = ver15_result.second;
        }

        auto ver2_result = run_ver2_only(current_order, current_plan, VER2_LIMIT);
        if (ver2_result.second.total_attacks < current_plan.total_attacks) {
            current_order = ver2_result.first;
            current_plan = ver2_result.second;
        }

        const vector<int> &final_order = current_order;
        const PlanDetail &final_plan = current_plan;

        ActionBuilder builder(H, A);
        vector<pair<int, int>> actions = builder.build_actions(final_order, final_plan);

        for (const auto &action : actions) { cout << action.first << ' ' << action.second << '\n'; }
    }
};

using namespace std;
using lint = long long;
using pint = std::pair<int, int>;
using plint = std::pair<lint, lint>;

struct fast_ios {
    fast_ios() {
        std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(20);
    };
} fast_ios_;

#include <cassert>
#include <limits>

// Rational number + {infinity(1 / 0), -infiity(-1 / 0), nan(0 / 0)} （有理数）
// Verified: Yandex Cup 2022 Final E https://contest.yandex.com/contest/42710/problems/K
template <class Int, bool AutoReduce = false> struct Rational {
    Int num, den; // den >= 0

    static constexpr Int my_gcd(Int a, Int b) {
        // return __gcd(a, b);
        if (a < 0) a = -a;
        if (b < 0) b = -b;
        while (a and b) {
            if (a > b) {
                a %= b;
            } else {
                b %= a;
            }
        }
        return a + b;
    }

    constexpr Rational(Int num = 0, Int den = 1) : num(num), den(den) { normalize(); }
    constexpr void normalize() noexcept {
        if constexpr (AutoReduce) { // reduction
            Int g = my_gcd(num, den);
            if (g) num /= g, den /= g;
        } else {
            if (den == 0) {
                if (num > 1) num = 1;
                if (num < -1) num = -1;
            }
        }
        if (den < 0) num = -num, den = -den; // denominator >= 0
    }

    constexpr bool is_finite() const noexcept { return den != 0; }
    constexpr bool is_infinite_or_nan() const noexcept { return den == 0; }

    constexpr Rational operator+(const Rational &r) const noexcept {
        if (is_infinite_or_nan() and r.is_infinite_or_nan()) return Rational(num + r.num, 0);
        return Rational(num * r.den + den * r.num, den * r.den);
    }
    constexpr Rational operator-(const Rational &r) const noexcept {
        if (is_infinite_or_nan() and r.is_infinite_or_nan()) return Rational(num - r.num, 0);
        return Rational(num * r.den - den * r.num, den * r.den);
    }
    constexpr Rational operator*(const Rational &r) const noexcept {
        return Rational(num * r.num, den * r.den);
    }
    constexpr Rational operator/(const Rational &r) const noexcept {
        return Rational(num * r.den, den * r.num);
    }
    constexpr Rational &operator+=(const Rational &r) noexcept { return *this = *this + r; }
    constexpr Rational &operator-=(const Rational &r) noexcept { return *this = *this - r; }
    constexpr Rational &operator*=(const Rational &r) noexcept { return *this = *this * r; }
    constexpr Rational &operator/=(const Rational &r) noexcept { return *this = *this / r; }
    constexpr Rational operator-() const noexcept { return Rational(-num, den); }
    constexpr Rational abs() const noexcept { return Rational(num > 0 ? num : -num, den); }

    constexpr Int floor() const {
        assert(is_finite());
        if (num > 0) {
            return num / den;
        } else {
            return -((-num + den - 1) / den);
        }
    }

    constexpr bool operator==(const Rational &r) const noexcept {
        if (is_infinite_or_nan() or r.is_infinite_or_nan()) {
            return num == r.num and den == r.den;
        } else {
            return num * r.den == r.num * den;
        }
    }

    constexpr bool operator!=(const Rational &r) const noexcept { return !(*this == r); }

    constexpr bool operator<(const Rational &r) const noexcept {
        if (is_infinite_or_nan() and r.is_infinite_or_nan())
            return num < r.num;
        else if (is_infinite_or_nan()) {
            return num < 0;
        } else if (r.is_infinite_or_nan()) {
            return r.num > 0;
        } else {
            return num * r.den < den * r.num;
        }
    }
    constexpr bool operator<=(const Rational &r) const noexcept {
        return (*this == r) or (*this < r);
    }
    constexpr bool operator>(const Rational &r) const noexcept { return r < *this; }
    constexpr bool operator>=(const Rational &r) const noexcept {
        return (r == *this) or (r < *this);
    }

    constexpr explicit operator double() const noexcept { return (double)num / (double)den; }
    constexpr explicit operator long double() const noexcept {
        return (long double)num / (long double)den;
    }
    template <class OStream> constexpr friend OStream &operator<<(OStream &os, const Rational &x) {
        return os << x.num << '/' << x.den;
    }
};

template <class Int> struct std::numeric_limits<Rational<Int, false>> {
    static constexpr Rational<Int, false> max() noexcept {
        return std::numeric_limits<Int>::max();
    }
    static constexpr Rational<Int, false> min() noexcept {
        return std::numeric_limits<Int>::min();
    }
    static constexpr Rational<Int, false> lowest() noexcept {
        return std::numeric_limits<Int>::lowest();
    }
};

using Rat = Rational<lint>;

#include <cassert>
#include <queue>
#include <vector>

namespace linear_sum_assignment {

template <class T> struct Result {
    T opt;
    std::vector<int> mate;
    std::vector<T> f, g; // dual variables
};

template <class T>
T augment(int nr, int nc, const std::vector<std::vector<T>> &C, std::vector<T> &f, std::vector<T> &g,
          int s, // source row
          std::vector<int> &mate,
          std::vector<int> &mate_inv, // duplicates are allowed (used for k-best algorithms)
          int fixed_rows = 0 // Ignore first rows and corresponding columns (used for k-best algorithms)
) {

    assert(0 <= s and s < nr);
    assert(mate.at(s) < 0);

    static std::vector<T> dist;
    static std::vector<int> prv;
    dist.resize(nc);
    prv.resize(nc);

    std::vector<bool> done(nc);

    for (int i = 0; i < fixed_rows; ++i) {
        if (int j = mate.at(i); j >= 0) done.at(j) = 1;
    }

    {
        int h = 0;
        while (done.at(h)) ++h;

        f.at(s) = C.at(s).at(h) - g.at(h);
        for (int j = h + 1; j < nc; ++j) {
            if (done.at(j)) continue;
            f.at(s) = std::min(f.at(s), C.at(s).at(j) - g.at(j));
        }
    }

    for (int j = 0; j < nc; ++j) {
        if (!done.at(j)) {
            dist.at(j) = C.at(s).at(j) - f.at(s) - g.at(j);
            prv.at(j) = -1;
        }
    }

    int t = -1;
    std::vector<int> stk;

    while (t == -1) {
        int j1 = -1;
        for (int j = 0; j < nc; ++j) {
            if (done.at(j)) continue;
            if (j1 == -1 or dist.at(j) < dist.at(j1) or
                (dist.at(j) == dist.at(j1) and mate_inv.at(j) < 0)) {
                j1 = j;
            }
        }

        if (mate_inv.at(j1) < 0) {
            t = j1;
            break;
        }

        done.at(j1) = 1;
        stk = {j1};

        while (!stk.empty()) {
            const int j2 = stk.back();
            const int i = mate_inv.at(j2);
            if (i < 0) {
                t = stk.back();
                break;
            }
            stk.pop_back();

            for (int j = 0; j < nc; ++j) {
                if (done.at(j)) continue;

                const T len = C.at(i).at(j) - f.at(i) - g.at(j);

                if (dist.at(j) > dist.at(j1) + len) {
                    dist.at(j) = dist.at(j1) + len;
                    prv.at(j) = j2;
                }

                if (len == T()) {
                    stk.push_back(j);
                    done.at(j) = 1;
                }
            }
        }
    }

    const T len = dist.at(t);

    f.at(s) += len;

    for (int i = 0; i < fixed_rows; ++i) {
        if (const int j = mate.at(i); j >= 0) done.at(j) = 0;
    }

    for (int j = 0; j < nc; ++j) {
        if (!done.at(j)) continue;

        g.at(j) -= len - dist.at(j);
    }

    for (int i = fixed_rows; i < nr; ++i) {
        const int j = mate.at(i);
        if (j < 0 or !done.at(j) or j >= nc) continue;
        f.at(i) += len - dist.at(j);
    }

    T ret = T();

    for (int cur = t; cur >= 0;) {
        const int nxt = prv.at(cur);
        if (nxt < 0) {
            mate_inv.at(cur) = s;
            mate.at(s) = cur;
            ret += C.at(s).at(cur);
            break;
        }
        const int i = mate_inv.at(nxt);

        ret += C.at(i).at(cur) - C.at(i).at(nxt);

        mate_inv.at(cur) = i;
        mate.at(i) = cur;
        cur = nxt;
    }

    return ret;
}

// Complexity: O(nr^2 nc)
template <class T> Result<T> _solve(int nr, int nc, const std::vector<std::vector<T>> &C) {

    assert(nr <= nc);

    std::vector<int> mate(nr, -1);
    std::vector<int> mate_inv(nc, -1);
    std::vector<T> f(nr), g(nc); // dual variables, f[i] + g[j] <= C[i][j] holds

    if (nr == 0 or nc == 0) return {T(), mate, f, g};

    if (nr == nc) {
        // Column reduction
        for (int j = nc - 1; j >= 0; --j) {
            g.at(j) = C.at(0).at(j) - f.at(0);
            int imin = 0;
            for (int i = 1; i < nr; ++i) {
                if (g.at(j) > C.at(i).at(j) - f.at(i)) {
                    imin = i;
                    g.at(j) = C.at(i).at(j) - f.at(i);
                }
            }

            if (mate.at(imin) < 0) {
                mate.at(imin) = j;
                mate_inv.at(j) = imin;
            } else if (g.at(j) < g.at(mate.at(imin))) {
                mate_inv.at(mate.at(imin)) = -1;
                mate.at(imin) = j;
                mate_inv.at(j) = imin;
            }
        }

        // Reduction transfer (can be omitted)
        if (nc > 1) {
            for (int i = 0; i < nr; ++i) {
                if (mate.at(i) < 0) continue;
                T best = C.at(i).at(0) - g.at(0), second_best = C.at(i).at(1) - g.at(1);
                int argbest = 0;
                if (best > second_best) std::swap(best, second_best), argbest = 1;

                for (int j = 2; j < nc; ++j) {
                    if (T val = C.at(i).at(j) - g.at(j); val < best) {
                        second_best = best;
                        best = val;
                        argbest = j;
                    } else if (val < second_best) {
                        second_best = val;
                    }
                }

                g.at(argbest) -= second_best - best;
                f.at(i) = second_best;
            }
        }

        // Augmenting row reduction: not implemented
    }

    // Augmentation
    for (int i = 0; i < nr; ++i) {
        if (mate.at(i) < 0) augment(nr, nc, C, f, g, i, mate, mate_inv);
    }

    T ret = 0;
    for (int i = 0; i < nr; ++i) ret += C.at(i).at(mate.at(i));

    return {ret, mate, std::move(f), std::move(g)};
}

// Jonker–Volgenant algorithm: find minimum weight assignment
// Dual problem (nr == nc): maximize sum(f) + sum(g) s.t. f_i + g_j <= C_ij
// Complexity: O(nr nc min(nr, nc))
template <class T> Result<T> solve(int nr, int nc, const std::vector<std::vector<T>> &C) {

    const bool transpose = (nr > nc);

    if (!transpose) return _solve(nr, nc, C);

    std::vector trans(nc, std::vector<T>(nr));

    for (int i = 0; i < nr; ++i) {
        for (int j = 0; j < nc; ++j) trans.at(j).at(i) = C.at(i).at(j);
    }

    auto [v, mate, f, g] = _solve(nc, nr, trans);

    std::vector<int> mate2(nr, -1);
    for (int j = 0; j < nc; ++j) {
        if (mate.at(j) >= 0) mate2.at(mate.at(j)) = j;
    }

    return {v, mate2, g, f};
}

} // namespace linear_sum_assignment

template <class T> struct best_assignments {

    struct Node {
        T opt;
        std::vector<int> mate;
        std::vector<T> f, g; // dual variables
        int fixed_rows;
        std::vector<int> banned_js; // C[fixed_rows][j] が inf となる j の集合

        // for priority queue
        // NOTE: reverse order
        bool operator<(const Node &rhs) const { return opt > rhs.opt; }

        linear_sum_assignment::Result<T> to_output(bool transpose) const {
            if (transpose) {
                std::vector<int> mate2(g.size(), -1);
                for (int i = 0; i < (int)mate.size(); ++i) mate2.at(mate.at(i)) = i;
                return {opt, mate2, g, f};
            } else {
                return {opt, mate, f, g};
            }
        }
    };

    bool transpose;
    int nr_, nc_;
    T inf;
    std::vector<std::vector<T>> C_, Ctmp_;
    std::priority_queue<Node> pq;

    best_assignments(int nr, int nc, const std::vector<std::vector<T>> &C, T inf)
        : transpose(nr > nc), inf(inf) {

        assert((int)C.size() == nr);
        for (int i = 0; i < nr; ++i) assert((int)C.at(i).size() == nc);

        nr_ = transpose ? nc : nr;
        nc_ = transpose ? nr : nc;

        C_.assign(nr_ + (nr_ != nc_), std::vector<T>(nc_, T()));
        for (int i = 0; i < nr; ++i) {
            for (int j = 0; j < nc; ++j) {
                C_.at(transpose ? j : i).at(transpose ? i : j) = C.at(i).at(j);
            }
        }

        Ctmp_ = C_;

        auto [opt, mate, f, g] = linear_sum_assignment::solve(C_.size(), nc, C_);

        pq.emplace(Node{opt, std::move(mate), std::move(f), std::move(g), 0, {}});
    }

    bool finished() const { return pq.empty(); }

    linear_sum_assignment::Result<T> yield() {
        assert(!pq.empty());

        const Node ret = pq.top();
        pq.pop();

        for (int fixed_rows = ret.fixed_rows; fixed_rows < nr_; ++fixed_rows) {
            std::vector<int> banned_js;
            if (fixed_rows == ret.fixed_rows) banned_js = ret.banned_js;

            const int s = fixed_rows;
            banned_js.push_back(ret.mate.at(s));

            if ((int)banned_js.size() >= nc_) continue;

            auto f = ret.f;
            auto g = ret.g;
            auto mate = ret.mate;

            std::vector<int> mate_inv(nc_, nr_);
            for (int i = 0; i < nr_; ++i) mate_inv.at(mate.at(i)) = i;

            std::vector<int> iscoldone(nc_);
            for (int i = 0; i < fixed_rows; ++i) iscoldone.at(mate.at(i)) = 1;

            for (int j : banned_js) Ctmp_.at(s).at(j) = inf;

            mate_inv.at(mate.at(s)) = -1;
            mate.at(s) = -1;

            auto aug = linear_sum_assignment::augment(
                nr_, nc_, Ctmp_, f, g, s, mate, mate_inv, fixed_rows);

            for (int j = 0; j < nc_; ++j) {
                if (mate_inv.at(j) < 0) { // nrows < ncols
                    g.at(j) = -f.back();
                    for (int i = fixed_rows; i < nr_; ++i) {
                        g.at(j) = std::min(g.at(j), Ctmp_.at(i).at(j) - f.at(i));
                    }
                }
            }

            if (Ctmp_.at(s).at(mate.at(s)) < inf) {
                pq.emplace(Node{
                    ret.opt + aug - C_.at(s).at(ret.mate.at(s)),
                    std::move(mate),
                    std::move(f),
                    std::move(g),
                    fixed_rows,
                    banned_js,
                });
            }

            for (int j : banned_js) Ctmp_.at(s).at(j) = C_.at(s).at(j);
        }

        return ret.to_output(transpose);
    }
};


#include <algorithm>
#include <numeric>
#include <utility>
#include <vector>

// UnionFind Tree (0-indexed), based on size of each disjoint set
struct UnionFind {
    std::vector<int> par, cou;
    UnionFind(int N = 0) : par(N), cou(N, 1) { iota(par.begin(), par.end(), 0); }
    int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (cou[x] < cou[y]) std::swap(x, y);
        par[y] = x, cou[x] += cou[y];
        return true;
    }
    int count(int x) { return cou[find(x)]; }
    bool same(int x, int y) { return find(x) == find(y); }
    std::vector<std::vector<int>> groups() {
        std::vector<std::vector<int>> ret(par.size());
        for (int i = 0; i < int(par.size()); ++i) ret[find(i)].push_back(i);
        ret.erase(std::remove_if(ret.begin(), ret.end(),
                                 [&](const std::vector<int> &v) { return v.empty(); }),
                  ret.end());
        return ret;
    }
};



constexpr int N = 200;
// array<int, N> H, C;
vector<int> H, C;
vector<vector<int>> A;
// vector A(N, vector<int>(N));
// array<array<int, N>, N> A;

int EvaluateSubsequence(const vector<int> &seq) {
    vector<pair<int, int>> yoryoku;

    int ret = H.at(seq.front());

    FOR(i, 1, seq.size()) {
        const int u = seq.at(i - 1);
        const int v = seq.at(i);

        int r = H.at(v) - A.at(u).at(v) * C.at(u);

        if (r > 0) {
            sort(ALL(yoryoku), [&](const auto &lhs, const auto &rhs) {
                const auto [lu, lr] = lhs;
                const auto [ru, rr] = rhs;
                return A.at(lu).at(v) < A.at(ru).at(v);
            });

            while (r > 0 and yoryoku.size()) {
                auto [u, rr] = yoryoku.back();
                const int d = A.at(u).at(v);
                if (d < 30) break;
                const int t = min(rr, (r + d - 1) / d);
                r -= t * d;
                yoryoku.back().second -= t;
                if (yoryoku.back().second == 0) yoryoku.pop_back();
            }

            if (r > 0) ret += r;
        } else {
            const int t = (H.at(v) + A.at(u).at(v) - 1) / A.at(u).at(v);
            const int rr = C.at(u) - t;
            yoryoku.emplace_back(u, rr);
        }
    }

    return ret;
}


#include <cstdint>
#include <vector>

uint32_t rand_int() // XorShift random integer generator
{
    static uint32_t x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    uint32_t t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
double rand_double() { return (double)rand_int() / UINT32_MAX; }

template <class T> void shuffle_vec(std::vector<T> &vec) {
    for (int i = 1; i < (int)vec.size(); ++i) {
        const int j = rand_int() % (i + 1);
        std::swap(vec.at(i), vec.at(j));
    }
}

pair<vector<int>, PlanDetail> ImprovePlan(const vector<int> &order, const PlanDetail &plan, bool shuffle_order) {
    vector<vector<int>> to(N);
    vector<vector<int>> rev(N);

    REP(i, N) {
        REP(j, N) {
            REP(_, plan.weapon_use.at(i).at(j)) {
                to.at(i).push_back(j);
                rev.at(j).push_back(i);
            }
        }
    }

    auto new_order = order;
    if (shuffle_order) {
        new_order.clear();
        vector<int> in(N);
        REP(i, N) {
            for (int j : to.at(i)) in.at(j)++;
        }

        vector<int> vs;
        REP(i, N) {
            if (in.at(i) == 0) vs.push_back(i);
        }

        REP(_, N) {
            const int idx = rand_int() % (int)vs.size();
            const int v = vs.at(idx);
            new_order.push_back(v);
            swap(vs.at(idx), vs.back());
            vs.pop_back();
            for (int u : to.at(v)) {
                in.at(u)--;
                if (in.at(u) == 0) vs.push_back(u);
            }
        }
    }

    vector<int> erased_js;
    REP(j, N) {
        if (rev.at(j).empty()) continue;
        if (plan.bare_hand.at(j) <= 10 or rand_int() % 2) {
            const int idx = rand_int() % rev.at(j).size();
            const int i = rev.at(j).at(idx);
            to.at(i).erase(find(ALL(to.at(i)), j));
            rev.at(j).erase(rev.at(j).begin() + idx);

            erased_js.push_back(j);
        }
    }

    vector<int> rem = H;
    REP(i, N) {
        for (int j : to.at(i)) {
            rem.at(j) -= A.at(i).at(j);
        }
    }
    for (auto &x : rem) chmax(x, 0);

    vector<int> xs;
    vector<int> head(N);
    REP(i, N) {
        REP(_, C.at(i) - (int)to.at(i).size()) {
            head.at(i) = xs.size();
            xs.push_back(i);
        }
    }

    vector<int> invpos(N, -1);
    REP(i, N) invpos.at(new_order.at(i)) = i;

    vector cost(erased_js.size(), vector<lint>(xs.size()));

    REP(r, cost.size()) REP(c, cost.at(0).size()) {
        const int i = xs.at(c);
        const int j = erased_js.at(r);
        if (invpos.at(i) < invpos.at(j)) {
            if (rem.at(j) > 0) {
                const int u = min(rem.at(j), A.at(i).at(j));
                cost.at(r).at(c) = -u;
            }
        }
    }


    auto [opt, mate, f, g] = linear_sum_assignment::solve(cost.size(), cost.at(0).size(), cost);
    REP(r, cost.size()) {
        const int j = erased_js.at(r);
        const int c = mate.at(r);
        if (c >= 0 and cost.at(r).at(c) < 0) {
            const int i = xs.at(c);
            to.at(i).push_back(j);
            rem.at(j) -= A.at(i).at(j);
        }
    }

    for (auto &x : rem) chmax(x, 0);

    vector result(N, vector<int>(N));
    REP(i, N) {
        for (int j : to.at(i)) {
            result.at(i).at(j)++;
        }
    }

    PlanDetail ret;
    ret.weapon_use = result;
    ret.bare_hand = rem;
    int total_attacks = 0;
    for (int x : rem) total_attacks += x;
    for (const auto &t : to) total_attacks += t.size();
    // REP(i, N) REP(j, N) total_attacks += result.at(i).at(j);
    ret.total_attacks = total_attacks;
    if (total_attacks <= plan.total_attacks) {
        return {new_order, ret};
    } else {
        return {order, plan};
    }
    // dbg(total_attacks);
    // return {order, ret};
}

int main(int argc, char *argv[]) {
    {
        int N_;
        cin >> N_;
        H.resize(N_);
        C.resize(N_);
        A.resize(N_, vector<int>(N_));
        cin >> H >> C >> A;
    }

    // vector<vector<pair<int, Rat>>> to(N);
    // vector<vector<pair<int, Rat>>> rev(N);
    // REP(i, N) REP(j, N) {
    //     if (i == j) continue;
    //     if (A.at(i).at(j) * C.at(i) >= H.at(j)) {
    //         const int t = (H.at(j) + A.at(i).at(j) - 1) / A.at(i).at(j);
    //         to.at(i).emplace_back(j, Rat{t, C.at(i)});
    //         rev.at(j).emplace_back(i, Rat{t, C.at(i)});
    //     }
    // }
    // REP(i, N) {
    //     dbg(make_tuple(i, to.at(i)));
    //     dbg(make_tuple(i, rev.at(i)));
    // }
    // REP(i, N) dbg(make_tuple(i, rev.at(i)));

    vector cost(N, vector<lint>(N));
    REP(i, N) REP(j, N) {
        if (i == j) {
            cost.at(i).at(j) = 1LL << 60;
        } else {
            const lint w = H.at(j) - A.at(i).at(j) * C.at(i);
            if (w > 0) {
                cost.at(i).at(j) = w;
            }
        }
    }

    Solver solver;
    solver.N = N;
    solver.H = H;
    solver.C = C;
    solver.A = A;

    // best_assignments<lint> bsa(N, N, cost, 1LL << 60);
    const auto [opt, mate, f, g] = linear_sum_assignment::solve(N, N, cost);

    vector<int> state;
    int state_eval = 1 << 30;
    {
        dbg(make_tuple(opt));

        UnionFind uf(N);
        REP(i, N) uf.unite(i, mate.at(i));
        for (auto g : uf.groups()) dbg(g.size());

        vector<int> visited(N);

        vector<vector<int>> subsequences;
        REP(i, N) {
            if (!visited.at(i)) {
                vector<int> seq;
                vector<int> costs;
                vector<int> hs;

                for (int cur = i; !visited.at(cur); cur = mate.at(cur)) {
                    visited.at(cur) = 1;
                    seq.push_back(cur);
                    costs.push_back(cost.at(cur).at(mate.at(cur)));
                    hs.push_back(H.at(cur));
                }
                // dbg(seq);
                // dbg(EvaluateSubsequence(seq));

                vector<int> best_seq = seq;
                int best_e = EvaluateSubsequence(seq);
                REP(_, seq.size()) {
                    rotate(seq.begin(), seq.begin() + 1, seq.end());
                    const int e = EvaluateSubsequence(seq);
                    if (chmin(best_e, e)) { best_seq = seq; }
                }
                // dbg(best_e);

                subsequences.push_back(best_seq);
                // dbg(costs);
                // dbg(hs);
            }
        }

        jdump("num_subsequences", subsequences.size());
        if (subsequences.size() <= 6) {
            sort(ALL(subsequences));
            do {
                vector<int> cand_state;
                for (auto s : subsequences) cand_state.insert(cand_state.end(), ALL(s));
                // dbg(cand_state);
                if (chmin(state_eval, solver.evaluate(cand_state))) { state = cand_state; }
            } while (next_permutation(ALL(subsequences)));
        } else {

            sort(subsequences.begin(), subsequences.end(),
                [&](const auto &lhs, const auto &rhs) { return lhs.size() > rhs.size(); });

            vector<int> cand_state;
            for (auto s : subsequences) cand_state.insert(cand_state.end(), ALL(s));
            // dbg(cand_state);
            if (chmin(state_eval, EvaluateSubsequence(cand_state))) { state = cand_state; }
        }
    }

    // auto [opt, mate, f, g] = linear_sum_assignment::solve(N, N, cost);
    // dbg(mate);
    // dbg(opt);


    // REP(i, N) dbg(make_tuple(i, cost.at(i).at(mate.at(i))));

    vector<int> best_order = solver.improve_order(state, 0.8);
    PlanDetail best_plan = solver.build_plan(best_order);
    dbg(best_plan.total_attacks);
    REP(_, 100) {
        tie(best_order, best_plan) = ImprovePlan(best_order, best_plan, true);
    }
    dbg(best_plan.total_attacks);

    REP(_, 6) {
        tie(best_order, best_plan) = solver.run_ver2_only(best_order, best_plan, 0.1);
        REP(_, 15) tie(best_order, best_plan) = ImprovePlan(best_order, best_plan, true);
        dbg(best_plan.total_attacks);
    }
    // tie(best_order, best_plan) = solver.run_ver2_only(best_order, best_plan, 0.8);
    // dbg(best_plan.total_attacks);

    dbg(best_plan.total_attacks);
    ActionBuilder builder(H, A);
    const vector<pair<int, int>> actions = builder.build_actions(best_order, best_plan);

    std::string solution;
    for (const auto &action : actions) {
        solution += std::to_string(action.first) + ' ' + std::to_string(action.second) + '\n';
        // cout << action.first << ' ' << action.second << '\n';
    }
    solution.pop_back();

    dump_onlinejudge(solution);

    const int score = accumulate(ALL(H), 0) - (int)actions.size() + 1;
    jdump("cost", actions.size());
    jdump("score", score);
    jdump("score150", score * 150);
    dbg(actions.size());
    dbg(score);
}

Submission Info

Compile Error

./Main.cpp:1668:14: warning: unused parameter 'argc' [-Wunused-parameter]
int main(int argc, char *argv[]) {
             ^
./Main.cpp:1668:26: warning: unused parameter 'argv' [-Wunused-parameter]
int main(int argc, char *argv[]) {
                         ^
2 warnings generated.

Judge Result