結果

問題 No.5020 Averaging
ユーザー 👑 hitonanodehitonanode
提出日時 2024-02-26 20:33:52
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 567 ms / 1,000 ms
コード長 21,324 bytes
コンパイル時間 2,412 ms
コンパイル使用メモリ 199,820 KB
実行使用メモリ 6,676 KB
スコア 45,150,922
最終ジャッジ日時 2024-02-26 20:34:25
合計ジャッジ時間 32,382 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 540 ms
6,676 KB
testcase_01 AC 544 ms
6,676 KB
testcase_02 AC 541 ms
6,676 KB
testcase_03 AC 543 ms
6,676 KB
testcase_04 AC 542 ms
6,676 KB
testcase_05 AC 565 ms
6,676 KB
testcase_06 AC 540 ms
6,676 KB
testcase_07 AC 567 ms
6,676 KB
testcase_08 AC 540 ms
6,676 KB
testcase_09 AC 540 ms
6,676 KB
testcase_10 AC 545 ms
6,676 KB
testcase_11 AC 539 ms
6,676 KB
testcase_12 AC 544 ms
6,676 KB
testcase_13 AC 546 ms
6,676 KB
testcase_14 AC 542 ms
6,676 KB
testcase_15 AC 543 ms
6,676 KB
testcase_16 AC 540 ms
6,676 KB
testcase_17 AC 543 ms
6,676 KB
testcase_18 AC 541 ms
6,676 KB
testcase_19 AC 540 ms
6,676 KB
testcase_20 AC 544 ms
6,676 KB
testcase_21 AC 543 ms
6,676 KB
testcase_22 AC 550 ms
6,676 KB
testcase_23 AC 542 ms
6,676 KB
testcase_24 AC 541 ms
6,676 KB
testcase_25 AC 542 ms
6,676 KB
testcase_26 AC 542 ms
6,676 KB
testcase_27 AC 541 ms
6,676 KB
testcase_28 AC 540 ms
6,676 KB
testcase_29 AC 541 ms
6,676 KB
testcase_30 AC 540 ms
6,676 KB
testcase_31 AC 540 ms
6,676 KB
testcase_32 AC 541 ms
6,676 KB
testcase_33 AC 542 ms
6,676 KB
testcase_34 AC 542 ms
6,676 KB
testcase_35 AC 541 ms
6,676 KB
testcase_36 AC 542 ms
6,676 KB
testcase_37 AC 540 ms
6,676 KB
testcase_38 AC 540 ms
6,676 KB
testcase_39 AC 542 ms
6,676 KB
testcase_40 AC 540 ms
6,676 KB
testcase_41 AC 540 ms
6,676 KB
testcase_42 AC 540 ms
6,676 KB
testcase_43 AC 544 ms
6,676 KB
testcase_44 AC 540 ms
6,676 KB
testcase_45 AC 540 ms
6,676 KB
testcase_46 AC 542 ms
6,676 KB
testcase_47 AC 542 ms
6,676 KB
testcase_48 AC 541 ms
6,676 KB
testcase_49 AC 566 ms
6,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 <array>
#include <cmath>
#include <cstdlib>
#include <vector>

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_;

constexpr int N = 45;

// void gen
constexpr lint AMIN = 100000000000000000;
constexpr lint AMAX = 1000000000000000000;
constexpr lint goalx = 500000000000000000;
constexpr lint goaly = 500000000000000000;

constexpr int MAXT = 50;


#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));
    }
}

#include <chrono>
#include <random>

struct rand_int_ {
    using lint = long long;
    std::mt19937 mt;
    rand_int_() : mt(std::chrono::steady_clock::now().time_since_epoch().count()) {}
    lint operator()(lint x) { return this->operator()(0, x); } // [0, x)
    lint operator()(lint l, lint r) {
        std::uniform_int_distribution<lint> d(l, r - 1);
        return d(mt);
    }
} rnd;

double eval_diversity(const array<lint, N> &A, const array<lint, N> &B, const bitset<N> &alives, lint cx, lint cy) {

    const int Z = 60;
    // const double r = 0.9;
    const double dec = 2.0;
    vector<double> hi(Z, -1e18);
    vector<double> invdsum(Z);
    REP(i, A.size()) {
        if (!alives[i]) continue;
        const lint a = A.at(i);
        const lint b = B.at(i);
        const double theta = atan2(b - cy, a - cx);
        int z = (theta / (2 * M_PI) + 0.5) * Z;
        // z = (z % Z + Z) % Z;
        const double dist = max(abs(a - cx), abs(b - cy)) + 1;
        // chmax(hi.at(z), -log10(dist));
        invdsum.at(z) += 1.0 / dist;
    }

    REP(z, Z) {
        if (invdsum.at(z)) hi.at(z) = log10(invdsum.at(z));
    }

    REP(_, 2) {
        FOR(i, 1, Z) {
            chmax(hi.at(i), hi.at(i - 1) - dec);
        }
        chmax(hi.at(0), hi.at(Z - 1) - dec);

        IFOR(i, 1, Z) {
            chmax(hi.at(i - 1), hi.at(i) - dec);
        }
        chmax(hi.at(Z - 1), hi.at(0) - dec);
    }
    return accumulate(ALL(hi), 0.0);
}


struct State {
    State *par = nullptr;
    std::vector<pint> par_op;  // par からどのような手でこれに到達するか
    int num_steps = 0;
    std::bitset<N> alives;
    std::array<lint, N> A, B;

    static State gen_root(const array<lint, N> &A, const array<lint, N> &B) {
        State s;
        s.alives.set();
        s.A = A;
        s.B = B;
        return s;
    }

    State gen_next(const vector<pint> ops) {
        State next;
        next.par = this;
        next.par_op = ops;
        next.num_steps = num_steps + (int)ops.size();
        next.alives = alives;
        next.A = A;
        next.B = B;
        for (auto [i, j] : ops) {
            lint tmpa = (next.A.at(i) + next.A.at(j)) / 2;
            lint tmpb = (next.B.at(i) + next.B.at(j)) / 2;
            next.A.at(i) = next.A.at(j) = tmpa;
            next.B.at(i) = next.B.at(j) = tmpb;
        }

        return next;
    }

    State try_drop(bool force) {
        lint sumx = 0, sumy = 0;
        const int nalive = alives.count();
        REP(i, N) {
            if (alives[i]) {
                sumx += A.at(i) - goalx;
                sumy += B.at(i) - goaly;
            }
        }
        const double error = 1.0 * max(abs(sumx), abs(sumy)) / nalive;
        int besti = -1;
        double besterror = error;
        // dbg(force);
        if (force) besterror = 1e30;
        FOR(i, 1, N) {
            if (!alives[i]) continue;
            // if ((sumx > 0) != (A.at(i) > goalx)) continue;
            // if ((sumy > 0) != (B.at(i) > goaly)) continue;
            // if (abs(sumx) < abs(A.at(i) - goalx)) continue;
            // if (abs(sumy) < abs(B.at(i) - goaly)) continue;
            const double errornew = 1.0 * max(abs(sumx - A.at(i) + goalx), abs(sumy - B.at(i) + goaly)) / (nalive - 1);
            if (chmin(besterror, errornew)) besti = i;

        }

        if (besti < 0) return *this;

        dbg(make_tuple("Drop", 1.0 * sumx / nalive, 1.0 * sumy / nalive, nalive, besti));
        State next = *this;
        next.alives[besti] = false;
        return next;
    }

    State step() {
        lint sumx = 0, sumy = 0;
        const int nalive = alives.count();
        REP(i, N) {
            if (alives[i]) {
                sumx += A.at(i);
                sumy += B.at(i);
            }
        }

        vector<pint> best_way;

        double min_error = 1e30;

        int xmini = -1, xmaxi = -1, ymini = -1, ymaxi = -1;
        lint xmin = AMAX + 1, xmax = -1e18, ymin = AMAX + 1, ymax = -1e18;

        REP(i, N) {
            if (!alives[i]) continue;
            if (chmin(xmin, A.at(i))) xmini = i;
            if (chmax(xmax, A.at(i))) xmaxi = i;
            if (chmin(ymin, B.at(i))) ymini = i;
            if (chmax(ymax, B.at(i))) ymaxi = i;
        }
        if (abs(ymax - ymin) > abs(xmax - xmin)) {
            best_way.emplace_back(ymini, ymaxi);
        } else {
            best_way.emplace_back(xmini, xmaxi);
        }
        // if (mode & 1) best_way.emplace_back(xmini, xmaxi);
        // if (mode & 2) best_way.emplace_back(ymini, ymaxi);
        return gen_next(best_way);
    }

    State primer() {
        vector<pint> best_ops;
        double best = AMAX;
        // const lint cx = goalx * 2 - A.at(0);
        const lint cx = goalx;
        // const lint cy = goaly * 2 - B.at(0);
        const lint cy = goaly;

        const lint d0 = max(abs(A.at(0) - cx), abs(B.at(0) - cy));

        auto Anxt = A, Bnxt = B;
        REP(i, N) REP(j, i) {
            if (!alives[i] or !alives[j]) continue;

            lint a = (A.at(i) + A.at(j)) / 2;
            lint b = (B.at(i) + B.at(j)) / 2;
            lint d = max(abs(a - cx), abs(b - cy));
            if (d > d0) continue;
            Anxt.at(i) = Anxt.at(j) = a;
            Bnxt.at(i) = Bnxt.at(j) = b;
            double after = eval_diversity(Anxt, Bnxt, alives, cx, cy);
            Anxt.at(i) = A.at(i);
            Anxt.at(j) = A.at(j);
            Bnxt.at(i) = B.at(i);
            Bnxt.at(j) = B.at(j);
            // double after = log(1.0 * d * d);
            if (chmin(best, -after)) best_ops = {{i, j}};
        }
        return gen_next(best_ops);
    }

    State greedy2() {
        lint best = AMAX;
        vector<pint> best_ops;
        // 0-i
        FOR(i, 1, N) {
            lint a = (A.at(0) + A.at(i)) / 2;
            lint b = (B.at(0) + B.at(i)) / 2;
            if (chmin(best, max(abs(a - goalx), abs(b - goaly)))) {
                best_ops = {{0, i}};
            }
        }

        // i-j, 0-i
        // i-j, 0-i, 0-j
        if (num_steps + 2 <= MAXT) {
            FOR(i, 1, N) FOR(j, 1, i) {
                const lint a1 = (A.at(i) + A.at(j)) / 2;
                const lint b1 = (B.at(i) + B.at(j)) / 2;
                {
                    const lint a = (A.at(0) + a1) / 2;
                    const lint b = (B.at(0) + b1) / 2;
                    if (chmin(best, max(abs(a - goalx), abs(b - goaly)))) {
                        best_ops = {{i, j}, {0, i}};
                    }

                    if (num_steps + 3 <= MAXT) {
                        const lint a2 = (a + a1) / 2;
                        const lint b2 = (b + b1) / 2;
                        if (chmin(best, max(abs(a2 - goalx), abs(b2 - goaly)))) {
                            best_ops = {{i, j}, {0, i}, {0, j}};
                        }
                    }
                }
            }
        }

        return gen_next(best_ops);
    }

    lint eval_linf() const { return max(abs(A.at(0) - goalx), abs(B.at(0) - goaly)); }
};

int calc_score(lint max_v1v2) {
    if (!max_v1v2) return 2000000 + 50;
    double sol = 2000000 - 100000 * log10(max_v1v2 + 1);
    return floor(sol);
}

void experiment() {
    constexpr int D = 28;
    vector<lint> A(D), B(D);
    REP(i, D) {
        A.at(i) = rnd(AMIN, AMAX);
        B.at(i) = rnd(AMIN, AMAX);
    }
    lint best_s = 0;
    lint best = 1LL << 60;
    FOR(S, 1, 1 << D) {
        lint asum = 0, bsum = 0, num = 0;
        REP(i, D) {
            if ((S >> i) & 1) {
                asum += A.at(i);
                bsum += B.at(i);
                ++num;
            }
        }
        asum /= num;
        bsum /= num;

        const lint eval = max(abs(asum - goalx), abs(bsum - goaly));

        if (chmin(best, eval)) {
            best_s = S;
        }

        if (__builtin_popcount(S + 1) == 1) {
            dbg(make_tuple(best, best_s, S));
        }
    }
}


vector<pint> generate_seq(const State *s) {
    vector<pint> res;
    while (s->par) {
        res.insert(res.end(), s->par_op.rbegin(), s->par_op.rend());
        s = s->par;
    }
    reverse(ALL(res));
    return res;
}

using SolutionState = vector<pint>;

double eval_l2(const array<long long, N> &Ainit, const array<long long, N> &Binit, const SolutionState &sol) {
    array<long long, N> A = Ainit, B = Binit;
    for (auto [i, j] : sol) {
        lint tmpa = (A.at(i) + A.at(j)) / 2;
        lint tmpb = (B.at(i) + B.at(j)) / 2;
        A.at(i) = A.at(j) = tmpa;
        B.at(i) = B.at(j) = tmpb;
    }
    const double dx = abs(A.at(0) - goalx), dy = abs(B.at(0) - goaly);
    return sqrt(dx * dx + dy * dy);
}

lint eval_linf(const array<long long, N> &Ainit, const array<long long, N> &Binit, const SolutionState &sol) {
    array<long long, N> A = Ainit, B = Binit;
    for (auto [i, j] : sol) {
        lint tmpa = (A.at(i) + A.at(j)) / 2;
        lint tmpb = (B.at(i) + B.at(j)) / 2;
        A.at(i) = A.at(j) = tmpa;
        B.at(i) = B.at(j) = tmpb;
    }
    const lint dx = abs(A.at(0) - goalx), dy = abs(B.at(0) - goaly);
    return max(dx, dy);
}

int main(int argc, char *argv[]) {
    // experiment();
    // int X = 0;
    // if (argc >= 2) { X = std::stoi(argv[1]); }
    {
        int n_;
        cin >> n_;
        assert(N == n_);
    }
    array<long long, N> A, B;
    {
        for (int i = 0; i < N; i++) {
            cin >> A.at(i) >> B.at(i);
        }
    }

    SolutionState state(N - 1);
    REP(i, N - 1) state.at(i) = {0, i + 1};
    auto best = state;

    double estate = eval_l2(A, B, state);
    double ebest = estate;

    const double Tbegin = 1e16, Tend = 100;

    REP(_, 2000000) {
        double T = Tbegin * pow(Tend / Tbegin, 1.0 * _ / 10000000);

        int a = rnd(N - 1), b = rnd(N - 1);
        swap(state.at(a), state.at(b));
        double ee = eval_l2(A, B, state);
        if (ee <= estate or exp((estate - ee) / T) > rand_double()) {
            estate = ee;

            if (chmin(ebest, estate)) {
                best = state;
                dbg(make_tuple(ebest, state));
            }
        } else {
            swap(state.at(a), state.at(b));
        }
    }

    dump_onlinejudge(best.size());
    for (auto [i, j] : best) {
        dump_onlinejudge(to_string(i + 1) + " " + to_string(j + 1));
    }

    // vector<State> states(10000);

    // states.at(0) = State::gen_root(A, B);
    // int h = 0;
    // bool mode = false;
    // while (states.at(h).num_steps < MAXT and states.at(h).alives.count() > 1) {
    //     const int nalive = states.at(h).alives.count();
    //     const int rem_turn = MAXT - states.at(h).num_steps;
    //     dbg(make_tuple(h, nalive, rem_turn));
    //     states.at(h + 1) = states.at(h).try_drop(rem_turn * 0.5 + 1 < nalive);
    //     ++h;
    //     // dbg(states.at(h).alives.count());

    //     // states.at(h + 1) = states.at(h).step(mode);
    //     // mode ^= 1;
    //     // ++h;

    //     if (states.at(h).num_steps < MAXT) {

    //         if (states.at(h).num_steps > MAXT * 0.9) {
    //             states.at(h + 1) = states.at(h).greedy2();
    //             ++h;
    //         } else {
    //             states.at(h + 1) = states.at(h).step();
    //             // states.at(h + 1) = states.at(h).primer();
    //             ++h;
    //         }
    //         mode ^= 1;
    //     }

    //     // if (h % 3 != 2 or states.at(h).num_steps < MAXT * 0.5) {
    //     //     states.at(h + 1) = states.at(h).primer();
    //     // } else {
    //     //     states.at(h + 1) = states.at(h).greedy2();
    //     // }
    //     // ++h;
    //     // dbg(make_tuple(states.at(h).num_steps, states.at(h).eval_linf()));
    // }

    // const State *goal_state = &states.at(h);
    // dbg(goal_state->alives);

    // auto sol = generate_seq(goal_state);

    // dump_onlinejudge(sol.size());
    // for (auto [i, j] : sol) {
    //     dump_onlinejudge(to_string(i + 1) + " " + to_string(j + 1));
    // }

    const lint cost = eval_linf(A, B, best);
    const int score = calc_score(cost);
    jdump("score", score);
    // dbg(cost);
    // dbg(score);
}
0