Submission #64985698

---

Source Code Expand

// bool TEST = true;
bool TEST = false;

int TARGET = 0;

const double T_START = 5000;
const double T_FINAL = 1;
const double T_RATE = T_FINAL / T_START;
const double TIME_LIMIT = 1.9;
const bool SA = 0;

using namespace std;
#include<bits/stdc++.h>
#include<fstream>
#include <iostream>
#include <cstdlib>
#include <dirent.h>

string cur_file; // 現在実行中の入力ファイル名

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);i++)
#define rrep(i,n) for(ll (i)=(ll)(n)-1;(i)>=0;i--)
#define range(i,start,end,step) for(ll (i)=start;(i)<(ll)(end);(i)+=(step))
#define rrange(i,start,end,step) for(ll (i)=start;(i)>(ll)(end);(i)+=(step))

#define dump(x)  cerr << "Line " << __LINE__ << ": " <<  #x << " = " << (x) << "\n";
#define spa << " " <<
#define cma << "," <<
#define fi first
#define se second
#define all(a)  (a).begin(),(a).end()
#define allr(a)  (a).rbegin(),(a).rend()

using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
 
template<typename T> using V = vector<T>;
template<typename T> using VV = V<V<T>>;
template<typename T, typename T2> using P = pair<T, T2>;
template<typename T, typename T2> using M = map<T, T2>;
template<typename T> using S = set<T>;
template<typename T, typename T2> using UM = unordered_map<T, T2>;
template<typename T> using PQ = priority_queue<T, V<T>, greater<T>>;
template<typename T> using rPQ = priority_queue<T, V<T>, less<T>>;
template<class T>vector<T> make_vec(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vec(size_t a, Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));}
template<class SS, class T> ostream& operator << (ostream& os, const pair<SS, T> v){os << "(" << v.first << ", " << v.second << ")"; return os;}
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<vector<T>> &v){ for(auto &e : v){os << e << "\n";} return os;}
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
 
template <class T> void UNIQUE(vector<T> &x) {sort(all(x));x.erase(unique(all(x)), x.end());}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
void fail() { cout << -1 << '\n'; exit(0); }
inline int popcount(const int x) { return __builtin_popcount(x); }
inline int popcount(const ll x) { return __builtin_popcountll(x); }
template<typename T> void debug(vector<vector<T>>&v){for(ll i=0;i<v.size();i++)
{cerr<<v[i][0];for(ll j=1;j<v[i].size();j++)cerr spa v[i][j];cerr<<"\n";}};
template<typename T> void debug(vector<T>&v){if(v.size()!=0)cerr<<v[0];
for(ll i=1;i<v.size();i++)cerr spa v[i];
cerr<<"\n";};
template<typename T> void debug(priority_queue<T>&v){V<T> vals; while(!v.empty()) {cerr << v.top() << " "; vals.push_back(v.top()); v.pop();} cerr<<"\n"; for(auto val: vals) v.push(val);}
template<typename T, typename T2> void debug(map<T,T2>&v){for(auto [k,v]: v) cerr << k spa v << "\n"; cerr<<"\n";}
template<typename T, typename T2> void debug(unordered_map<T,T2>&v){for(auto [k,v]: v) cerr << k spa v << "\n";cerr<<"\n";}
V<int> listrange(int n) {V<int> res(n); rep(i,n) res[i]=i; return res;}

template<typename T> P<T,T> divmod(T a, T b) {return make_pair(a/b, a%b);}
template<typename T> T SUM(V<T> a){T val(0); for (auto v : a) val += v; return val;}


#define VISUALIZE // 提出時にはここをコメントアウトすること。そうしないとTLEする。

#ifdef VISUALIZE

bool VISUALIZE_FLAG = true;
// std::ofstream cout << "#svis "("VisCommands.txt");


// ビジュアライザ上で表示される時間を指定します
#define vis_time(t) cout << "#svis " << "time = " << (t) << ";" << endl;
// ビジュアライザ上で常に表示されます
#define vis_always(t) vis_time(-1)

// リファレンス https://p5js.org/reference/
// Web上のエディタ https://editor.p5js.org/
#define vis_arc(x, y, w, h, start, stop) cout << "#svis " << "arc( " << (x) << ", " << (y) << ", " << (w) << ", " << (h) << ", " << (start) << ", " << (stop) << ");" << endl;
#define vis_ellipse(x, y, w, h) cout << "#svis " << "ellipse( " << (x) << ", " << (y) << ", " << (w) << ", " << (h) << ");" << endl;
#define vis_circle(x, y, d) cout << "#svis " << "circle( " << (x) << ", " << (y) << ", " << (d) << ");" << endl;
#define vis_line(x1, y1, x2, y2) cout << "#svis " << "line( " << (x1) << ", " << (y1) << ", " << (x2) << ", " << (y2) << ");" << endl;
#define vis_point(x, y) cout << "#svis " << "point( " << (x) << ", " << (y) << ");" << endl;
#define vis_quad(x1, y1, x2, y2, x3, y3, x4, y4) cout << "#svis " << "quad( " << (x1) << ", " << (y1) << ", " << (x2) << ", " << (y2) << ", " << (x3) << ", " << (y3) << ", " << (x4) << ", " << (y4) << ");" << endl;
#define vis_rect(x, y, w, h) cout << "#svis " << "rect( " << (x) << ", " << (y) << ", " << (w) << ", " << (h) << ");" << endl;
#define vis_square(x, y, s) cout << "#svis " << "square( " << (x) << ", " << (y) << ", " << (s) << ");" << endl;
#define vis_triangle(x1, y1, x2, y2, x3, y3) cout << "#svis " << "triangle( " << (x1) << ", " << (y1) << ", " << (x2) << ", " << (y2) << ", " << (x3) << ", " << (y3) << ");" << endl;

#define vis_background(r, g, b) cout << "#svis " << "background(" << (r) << ", " << (g) << ", " << (b) << ");" << endl;
#define vis_clear() cout << "#svis " << "clear();" << endl;
#define vis_colorMode(mode, max1, max2, max3, maxA) cout << "#svis " << "colorMode(" << (mode) << ", " << (max1) << ", " << (max2) << ", " << (max3) << ", " << (maxA) << ");" << endl;
#define vis_fill(r, g, b, a) cout << "#svis " << "fill(" << (r) << ", " << (g) << ", " << (b) << ", " << (a) << ");" << endl;
#define vis_noFill() cout << "#svis " << "noFill();" << endl;
#define vis_noStroke() cout << "#svis " << "noStroke();" << endl;
#define vis_stroke(r, g, b, a) cout << "#svis " << "stroke(" << (r) << ", " << (g) << ", " << (b) << ", " << (a) << ");" << endl;
#define vis_erase() cout << "#svis " << "erase();" << endl;
#define vis_noErase() cout << "#svis " << "noErase();" << endl;

#define vis_textAlign(alignX, alignY) cout << "#svis " << "textAlign(" << (alignX) << ", " << (alignY) << ");" << endl;
#define vis_textLeading(leading) cout << "#svis " << "textLeading(" << (leading) << ");" << endl;
#define vis_textSize(size) cout << "#svis " << "textSize(" << (size) << ");" << endl;
#define vis_textStyle(style) cout << "#svis " << "textStyle(" << (style) << ");" << endl;
#define vis_textWidth(text) cout << "#svis " << "textWidth(" << (text) << ");" << endl;
#define vis_textAscent() cout << "#svis " << "textAscent();" << endl;
#define vis_textDescent() cout << "#svis " << "textDescent();" << endl;
#define vis_textWrap(wrap) cout << "#svis " << "textWrap(" << (wrap) << ");" << endl;
#define vis_text(str, x, y) cout << "#svis " << "text("               \
                                       << "\"" << (str) << "\"" \
                                       << ", " << (x) << ", " << (y) << ");" << endl;

#else //  VISUALIZE

bool VISUALIZE_FLAG = false;
#define vis_time(t)
#define vis_always(t)

#define vis_arc(x, y, w, h, start, stop)
#define vis_ellipse(x, y, w, h)
#define vis_circle(x, y, d)
#define vis_line(x1, y1, x2, y2)
#define vis_point(x, y)
#define vis_quad(x1, y1, x2, y2, x3, y3, x4, y4)
#define vis_rect(x, y, w, h)
#define vis_square(x, y, s)
#define vis_triangle(x1, y1, x2, y2, x3, y3)

#define vis_background(r, g, b)
#define vis_clear()
#define vis_colorMode(mode, max1, max2, max3, maxA)
#define vis_fill(r, g, b, a)
#define vis_noFill()
#define vis_noStroke()
#define vis_stroke(r, g, b, a)
#define vis_erase()
#define vis_noErase()

#define vis_textAlign(alignX, alignY)
#define vis_textLeading(leading)
#define vis_textSize(size)
#define vis_textStyle(style)
#define vis_textWidth(text)
#define vis_textAscent()
#define vis_textDescent()
#define vis_textWrap(wrap)
#define vis_text(str, x, y)

#endif // VISUALIZE
//----------- p5visualizerのマクロ（ここまで） -------------


const ll INF = (1ll<<62);
// const ld EPS   = 1e-10;
// const ld PI    = acos(-1.0);

static unsigned int xxx=123456789,yyy=362436069,zzz=521288629,www=88675123;
unsigned int randxor()
{
    unsigned int t;
    t=(xxx^(xxx<<11));xxx=yyy;yyy=zzz;zzz=www; return( www=(www^(www>>19))^(t^(t>>8)) );
}
V<unsigned int> _rs;
const int RAND_SIZE = 100000;
int _rs_ind = 0;
inline unsigned int randint() {
    ++_rs_ind;
    if (_rs_ind==RAND_SIZE) _rs_ind = 0;
    return _rs[_rs_ind];
}

int random_select(V<ll> &vals) {
    // vals の重みで [0, vals.size()) からサンプリング
    ll s = 0;
    for (auto v : vals) s += v;
    ll val = randint()%s;
    rep(i, vals.size()) {val -= vals[i]; if (val<=0) return i;}
    return vals.size()-1;
}
const int BUNBO = 1e9;
double uniform_rand () {
    return double(randxor()%BUNBO+1) / double(BUNBO);
}

V<double> TIME_LIST;
auto _START_TIME = chrono::system_clock::now();
double current_time() {
    return chrono::duration_cast<chrono::microseconds>(chrono::system_clock::now() - _START_TIME).count() * 1e-6;
}

// ソルバークラスのひな型
struct Board {
    // 焼きなましの雛形
    inline double temp(double t_now, double tl, double t0) {
        // 指数減衰
        return T_START * pow(T_RATE, ((t_now - t0) / (tl - t0)));
    }
    int try_update_0(double thred) {
        // スコア差分 thred より良ければ内部状態を更新する
        // 更新したかの 0/1 を返す
        return 0;
    }
    int try_update_1(double thred) {
        // スコア差分 thred より良ければ内部状態を更新する
        // 更新したかの 0/1 を返す
        return 0;
    }
    void sa(double tl) {
        // 時間制限 tl まで実行する
        int rc = 0;
        int suc = 0;
        V<int> suc_lst(5); // 各近傍の成功数のカウント
        V<int> rc_lst(5); // 各近傍の成功数のカウント
        double t_now;
        double t0 = current_time();
        while (true) {
            if ((t_now=current_time())>=tl) break;
            double thred;
            if (SA) thred = log(uniform_rand()) * temp(t_now, tl, t0);
            else thred = 0;
            int r = randint()%100;
            P<int,int> res; // {近傍種類, 成否}
            if (r<15) res = {0, try_update_0(thred)};
            else res = {1, try_update_1(thred)};
            if (res.second) {
                suc_lst[res.first]++;
                suc++;
            }
            rc_lst[res.first]++;
            rc++;
        }
        debug(rc_lst);
        debug(suc_lst);
    }
};


using Real = double;
const Real EPS = 1e-8;
const Real PI = acos(static_cast< Real >(-1));

enum {
OUT, ON, IN
};
inline int sign(const Real &r) {
return r <= -EPS ? -1 : r >= EPS ? 1 : 0;
}
inline bool equals(const Real &a, const Real &b) {
return sign(a - b) == 0;
}

enum TrashType {
    BURNABLE = 0,
    NON_BURNABLE = 1,
    RECYCLABLE = 2
};

struct Trash {
    int x, y;
    int ttype; // 0 = burnable, 1 = non-burnable, 2 = recyclable
    Trash(int x, int y, int ttype): x(x), y(y), ttype(ttype) {}
};

class InputManager {
public:
    int X, Y, Z; // Counts of each trash type
    vector<Trash> trashes;

    void read_input() {
        cin >> X >> Y >> Z;
        int total = X + Y + Z;
        for (int i = 0; i < total; ++i) {
            int x, y;
            cin >> x >> y;
            int ttype;
            if (i < X) ttype = BURNABLE;
            else if (i < X + Y) ttype = NON_BURNABLE;
            else ttype = RECYCLABLE;
            trashes.emplace_back(x, y, ttype);
        }
    }

    vector<Trash> get_trashes_by_type(int ttype) const {
        vector<Trash> result;
        for (const auto& t : trashes) {
            if (t.ttype == ttype) result.push_back(t);
        }
        return result;
    }
};

struct MoveCommand {
    vector<pair<int, int>> hands; // size must be 4
    MoveCommand(const vector<pair<int, int>>& hands): hands(hands) {
        assert(hands.size() == 4);
    }
};

class OutputManager {
public:
    vector<MoveCommand> commands;

    void set_initial_positions(pair<int, int> takahashi_l, pair<int, int> takahashi_r,
                                pair<int, int> aoki_l, pair<int, int> aoki_r) {
        commands.emplace_back(vector<pair<int, int>>{takahashi_l, takahashi_r, aoki_l, aoki_r});
    }

    void add_move(pair<int, int> takahashi_l, pair<int, int> takahashi_r,
                  pair<int, int> aoki_l, pair<int, int> aoki_r) {
        commands.emplace_back(vector<pair<int, int>>{takahashi_l, takahashi_r, aoki_l, aoki_r});
    }

    void print_output() const {
        for (const auto& cmd : commands) {
            for (int i = 0; i < 4; ++i) {
                cout << cmd.hands[i].first << " " << cmd.hands[i].second;
                if (i < 3) cout << " ";
            }
            cout << '\n';
        }
    }
};


// 判定関数
long long orient(pair<int, int> a, pair<int, int> b, pair<int, int> p) {
    return 1LL * (b.first - a.first) * (p.second - a.second) - 1LL * (b.second - a.second) * (p.first - a.first);
}

bool in_triangle(pair<int, int> a, pair<int, int> b, pair<int, int> c, pair<int, int> p) {
    if(a==b && b == c && a != p) return false; 
    long long c1 = orient(a, b, p);
    long long c2 = orient(b, c, p);
    long long c3 = orient(c, a, p);
    return (c1 >= 0 && c2 >= 0 && c3 >= 0) || (c1 <= 0 && c2 <= 0 && c3 <= 0);
}

double dist(pair<int, int> a, pair<int, int> b) {
    return hypot(a.first - b.first, a.second - b.second);
}
pair<bool, int> validate_and_score(const InputManager& input, const OutputManager& output) {
    set<pair<int, int>> burnable_set, nonburnable_set, recyclable_set;
    for (const auto& t : input.trashes) {
        if (t.ttype == BURNABLE) burnable_set.emplace(t.x, t.y);
        else if (t.ttype == NON_BURNABLE) nonburnable_set.emplace(t.x, t.y);
        else recyclable_set.emplace(t.x, t.y);
    }

    if (output.commands.empty()) return {false, 0};
    auto prev = output.commands[0].hands;

    double total_time = 0.0;
    for (size_t i = 1; i < output.commands.size(); ++i) {
        auto curr = output.commands[i].hands;

        auto a1 = prev[0], a2 = prev[1], a3 = curr[0], a4 = curr[1];
        auto b1 = prev[2], b2 = prev[3], b3 = curr[2], b4 = curr[3];

        set<pair<int, int>> new_recyclable;
        for (const auto& p : recyclable_set) {
            if (in_triangle(a1, a2, a3, p) || in_triangle(a3, a2, a4, p) ||
                in_triangle(b1, b2, b3, p) || in_triangle(b3, b2, b4, p)) {
                    cerr << in_triangle(a1, a2, a3, p) <<" " <<  in_triangle(a3, a2, a4, p)  << endl;
                    cerr << in_triangle(b1, b2, b3, p)  << " "  <<  in_triangle(b3, b2, b4, p) << endl;
                    cerr << a1 << a2 << a3 << a4 << b1 << b2 << b3 << b4 << p << endl;
                    return {false, 0};
            }
            new_recyclable.insert(p);
        }
        recyclable_set = move(new_recyclable);

        set<pair<int, int>> new_burnable;
        for (const auto& p : burnable_set) {
            if (!(in_triangle(a1, a2, a3, p) || in_triangle(a3, a2, a4, p))) {
                new_burnable.insert(p);
            }
        }
        burnable_set = move(new_burnable);

        set<pair<int, int>> new_nonburnable;
        for (const auto& p : nonburnable_set) {
            if (!(in_triangle(b1, b2, b3, p) || in_triangle(b3, b2, b4, p))) {
                new_nonburnable.insert(p);
            }
        }
        nonburnable_set = move(new_nonburnable);

        double takahashi_cost = dist(prev[0], curr[0]) + dist(prev[1], curr[1]);
        double aoki_cost = dist(prev[2], curr[2]) + dist(prev[3], curr[3]);
        total_time += max(takahashi_cost, aoki_cost);

        prev = curr;
    }
    cerr << "---" << endl;
    for(auto pos: burnable_set)
        cerr << pos << endl;
    cerr << "---" << endl;
    
    cerr << "---" << endl;
    for(auto pos: nonburnable_set)
        cerr << pos << endl;
    cerr << "---" << endl;
    

    if (!burnable_set.empty() || !nonburnable_set.empty()) return {false, 0};

    if (total_time <= 1e8) {
        int score = round(1e6 * (1 + log2(1e8 / total_time)));
        return {true, score};
    } else {
        int total_collected = input.X + input.Y + input.Z - recyclable_set.size();
        int max_possible = input.X + input.Y + input.Z;
        int score = round(1e6 * (double(total_collected) / max_possible));
        return {true, score};
    }
}

// ユーティリティ：ユークリッド距離
double euclidean(pair<int, int> a, pair<int, int> b) {
    return hypot(a.first - b.first, a.second - b.second);
}

// 与えられた点集合 points の凸包（反時計回り）を構築
vector<pair<int, int>> compute_convex_hull(vector<pair<int, int>> points) {
    sort(points.begin(), points.end());
    points.erase(unique(points.begin(), points.end()), points.end());

    int n = points.size();
    if (n <= 2) return points;

    vector<pair<int, int>> hull;
    for (int phase = 0; phase < 2; ++phase) {
        int start = hull.size();
        for (int i = 0; i < n; ++i) {
            while (hull.size() >= start + 2 && orient(hull[hull.size() - 2], hull[hull.size() - 1], points[i]) <= 0)
                hull.pop_back();
            hull.push_back(points[i]);
        }
        hull.pop_back();
        reverse(points.begin(), points.end());
    }
    return hull;
}

// ゴミが含まれていたら true
bool is_invalid_triangle(pair<int, int> a, pair<int, int> b, pair<int, int> c, const set<pair<int, int>>& forbidden) {
    for (const auto& p : forbidden) {
        if (in_triangle(a, b, c, p)) return true;
    }
    return false;
}

// 凸包構築（target の index から始めて資源・他人ゴミの混入を避ける）
vector<pair<int, int>> build_safe_convex_hull(const vector<pair<int, int>>& target, int& start_index,
                                              const set<pair<int, int>>& forbidden) {
    vector<pair<int, int>> region;
    for (int i = start_index; i < target.size(); ++i) {
        region.push_back(target[i]);
        auto hull = compute_convex_hull(region);
        bool valid = true;
        int m = hull.size();
        for (int j = 0; j < m; ++j) {
            pair<int, int> a = hull[j];
            pair<int, int> b = hull[(j + 1) % m];
            pair<int, int> c = target[i];
            if (is_invalid_triangle(a, b, c, forbidden)) {
                valid = false;
                break;
            }
        }
        if (!valid) {
            region.pop_back();
            break;
        } else {
            start_index = i + 1;
        }
    }
    return compute_convex_hull(region);
}

// 掃除経路を構成（現在位置→スタート→凸包→合流点）
// 結果は「一人分の手の動き」のみ生成する（後で統合するため）
pair<vector<pii>, vector<pii>> build_hand_path(pair<int, int> cur_pos,
                                       const vector<pair<int, int>>& hull,
                                       const pair<int, int>& target_next) {
    vector<pair<int, int>> pathA;
    vector<pii> pathB;
    if (hull.empty()) return make_pair(pathA, pathB);

    int start_idx = 0;
    double min_dist = euclidean(cur_pos, hull[0]);
    for (int i = 1; i < hull.size(); ++i) {
        double d = euclidean(cur_pos, hull[i]);
        if (d < min_dist) {
            min_dist = d;
            start_idx = i;
        }
    }

    int end_idx = 0;
    min_dist = euclidean(target_next, hull[0]);
    for(int i=1; i<hull.size(); i++) {
        double d = euclidean(target_next, hull[i]);
        if(d < min_dist) {
            min_dist = d;
            end_idx = i;
        }

    }


    for (int i = 0; i < hull.size() + 1; ++i) {
        int idx = (start_idx + i) % hull.size();
        pathA.push_back(hull[idx]);
        if(idx == end_idx && start_idx != end_idx) break;
    }
    for(int i=0; i<hull.size() + 1; i++) {
        int idx = (start_idx  + 2 * hull.size() - i) % hull.size();
        pathB.push_back(hull[idx]);
        if(idx == end_idx) break;
    }

    // prepend current position and return
    // pathA.insert(pathA.begin(), cur_pos);
    assert(pathA.size() + pathB.size() == hull.size() + 2);
    return make_pair(pathA, pathB);
}

void padding(vector<pii> &dat, pii elem, int border) {
    while(dat.size() < border) dat.push_back(elem);

}

// 高橋と青木の target を元に経路を作り、時間ごとに両者を進めて OutputManager に記録
void simulate_routes(const vector<pair<int, int>>& takahashi_target,
                     const vector<pair<int, int>>& aoki_target,
                     const set<pair<int, int>>& forbidden,
                     OutputManager& out) {
    int t_index = 0, a_index = 0;
    pair<int, int> t_pos = {0, 0}, a_pos = {0, 0};
    if(takahashi_target.size() > 0)
        t_pos = takahashi_target[0];
    if(aoki_target.size() > 0)
        a_pos = aoki_target[0];


    set<pii> forbidden_t;
    set<pii> forbidden_a;
    for(auto pos: forbidden) {
        forbidden_a.insert(pos);
        forbidden_t.insert(pos);
    }

    
    for(auto pos: takahashi_target) {
        forbidden_a.insert(pos);
    }
    for(auto pos: aoki_target) {
        forbidden_t.insert(pos);
    }

    while (t_index < takahashi_target.size() || a_index < aoki_target.size()) {
        
        int prev_t_index = t_index;
        int prev_a_index = a_index;
        cerr << t_index << " " << a_index << endl;
        vector<pair<int, int>> t_hull = build_safe_convex_hull(takahashi_target, t_index, forbidden_t);
        vector<pair<int, int>> a_hull = build_safe_convex_hull(aoki_target, a_index, forbidden_a);

        pair<int, int> t_next = (t_index < takahashi_target.size() ? takahashi_target[t_index] : t_pos);
        pair<int, int> a_next = (a_index < aoki_target.size() ? aoki_target[a_index] : a_pos);

        auto t_path = build_hand_path(t_pos, t_hull, t_next);
        auto  a_path = build_hand_path(a_pos, a_hull, a_next);
        auto t_path_left = t_path.first;
        auto t_path_right = t_path.second;
        auto a_path_left = a_path.first;
        auto a_path_right = a_path.second;
        
        padding(t_path_left, t_pos,1);
        padding(t_path_right, t_pos,1);
        padding(a_path_left, a_pos,1);
        padding(a_path_right, a_pos,1);

        // 両者のパスの長さをそろえて補完（短い側は最後の点を繰り返す）
        int steps = max({t_path_left.size(), t_path_right.size(), a_path_left.size(), a_path_right.size()});
        padding(t_path_left, t_path_left.back(),steps);
        padding(t_path_right, t_path_right.back(),steps);
        padding(a_path_left, a_path_left.back(),steps);
        padding(a_path_right, a_path_right.back(),steps);


        for (int i = 0; i < steps; ++i) {
            vector<pair<int, int>> hands(4);
            hands[0] = t_path_left[i];  // 高橋左手
            hands[1] = t_path_right[i];      // 高橋右手
            hands[2] = a_path_left[i];  // 青木左手
            hands[3] = a_path_right[i];      // 青木右手
            out.commands.push_back(MoveCommand(hands));
        }
        // out.commands.push_back(MoveCommand({t_path[1], t_path[1], a_path[1], a_path[1]}));


        assert(t_path_left.back() == t_path_right.back());
        assert(a_path_left.back() == a_path_right.back());
        // 現在位置更新
        if (!t_path_left.empty()) t_pos = t_path_left.back();
        if (!a_path_left.empty()) a_pos = a_path_left.back();
        
        for(int i = prev_a_index; i<a_index; i++) {
            forbidden_t.erase(aoki_target[i]);
        }
    
        for(int i = prev_t_index; i<t_index; i++) {
            forbidden_a.erase(takahashi_target[i]);
            // cerr <<"cleared " <<  takahashi_target[i] << endl;
        }
    }
}
mt19937 rng(0);

// TSP 用 2-opt 法による経路改善
vector<pair<int, int>> tsp_2opt( vector<pair<int, int>>& points, int iter = 10000) {
    int n = points.size();
    if(n==0) return points;
    vector<int> route(n);
    iota(route.begin(), route.end(), 0);

    auto total_length = [&](const vector<int>& r) {
        double sum = 0;
        for (int i = 0; i < n - 1; ++i) {
            sum += euclidean(points[r[i]], points[r[i + 1]]);
        }
        sum += euclidean(points[r[0]], points[r[n-1]]);
        return sum;
    };

    double best = total_length(route);

    for (int it = 0; it < iter; ++it) {
        if(it % 10 == 0) {
            vector<pii> tmp;
            for(int i=n/2; i<n; i++)
                tmp.push_back(points[i]);
            for(int i=0; i<n/2; i++)
                tmp.push_back(points[i]);
            points = tmp;
        }
        int a = uniform_int_distribution<int>(0, n - 2)(rng);
        int b = uniform_int_distribution<int>(a + 1, n - 1)(rng);
        reverse(route.begin() + a, route.begin() + b + 1);
        double new_len = total_length(route);
        if (new_len < best) {
            best = new_len;
        } else {
            reverse(route.begin() + a, route.begin() + b + 1); // rollback
        }
    }

    vector<pair<int, int>> reordered;
    for (int i : route) reordered.push_back(points[i]);
    return reordered;
}

// TSP 初期解：貪欲法で近い点を選んでいく（その後 2-opt に渡せる）
vector<pair<int, int>> tsp_greedy(const vector<pair<int, int>>& points) {
    int n = points.size();
    if (n == 0) return {};

    vector<bool> used(n, false);
    vector<pair<int, int>> path;
    path.push_back(points[0]);
    used[0] = true;

    for (int step = 1; step < n; ++step) {
        int best_idx = -1;
        double best_dist = 1e18;
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                double d = euclidean(path.back(), points[i]);
                if (d < best_dist) {
                    best_dist = d;
                    best_idx = i;
                }
            }
        }
        path.push_back(points[best_idx]);
        used[best_idx] = true;
    }
    return path;
}

void get_randomize(vector<pii>& dat) {
    if(dat.size() == 0)
        return ;
    vector<pii> ret;

    int idx = rng() % dat.size();
    for(int i=idx; i<dat.size(); i++) ret.push_back(dat[i]);
    for(int i=0; i<idx; i++) ret.push_back(dat[i]);
    dat = ret;
}




ll Main() {
    
    InputManager im;
    im.read_input();

    auto burnable = im.get_trashes_by_type(BURNABLE);
    auto unburnable = im.get_trashes_by_type(NON_BURNABLE);

    pair<int, int> POS_CORNER = pii(0, 0);

    vector<pii> tmp;
    
    for(auto pos: burnable) {
        tmp.push_back(pii(pos.x, pos.y));
    }
    tmp = tsp_greedy(tmp);
    auto burnable2 = tsp_2opt(tmp);
    

    tmp.clear();
    for(auto pos: unburnable) {
        tmp.push_back(pii(pos.x, pos.y));
    }
    tmp = tsp_greedy(tmp);
    auto unburnable2 = tsp_2opt(tmp);
    

    auto recycle = im.get_trashes_by_type(RECYCLABLE);
    set<pii> recycle2;
    for(auto pos: recycle)
        recycle2.insert(pii(pos.x, pos.y));

    cerr << "aaa" << endl;

    OutputManager om_best;
    double score_best = -10;
    while(true) {
        OutputManager om;

        simulate_routes(burnable2, unburnable2, recycle2, om);

        auto res = validate_and_score(im, om);
        cerr << res << endl;
        if(score_best < res.second) {
            score_best = res.second;
            om_best.commands = om.commands;
        }
        
        get_randomize(burnable2);
        get_randomize(unburnable2);
        if(current_time() > 1.5) break;

        if(!res.first) continue;
    }
    om_best.print_output();
    cerr << validate_and_score(im, om_best) << endl;

    return 0;
}

V<string> search_dir(const char *path, int l, int l2){
    DIR *dp;
    dp = opendir(path);
    if (dp==NULL) exit(1);
    dirent* entry = readdir(dp);
    V<string> fs;
    while (entry != NULL){
        string s = string(path, l) + string(entry->d_name, l2);
        if (s[s.length()-1]=='t') {
            fs.push_back(s);
        }
        entry = readdir(dp);
    }
    return fs;
}

void Main_test(int argc, char* argv[]){
    // テスト時はこちらが走る
    // TARGET>=0 が指定されている場合、その番号のみを実行する
    // コマンドライン引数が与えられている場合、TARGET に代入する
    V<string> fs = search_dir("./in/", 5, 8); // (ディレクトリ名長さ, ファイル名長さ)
    ll s_all = 0;
    int cc = 0;
    if (argc>1) TARGET = atoi(argv[1]);
    if (TARGET>=0) fs = {fs[TARGET]};
    for (auto f : fs) {
        cur_file = f;
        cout << f << endl;
        // std::ifstream in(f);
        // std::cin.rdbuf(in.rdbuf());  
        _START_TIME = chrono::system_clock::now();
        std::cout << std::fixed << std::setprecision(15);
        s_all += Main();
    }
    cout << double(s_all) / fs.size() << endl;
}


int main(int argc, char* argv[]){
    std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
    if (TEST) Main_test(argc, argv);
    else Main();
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘V<int> listrange(int)’:
Main.cpp:21:25: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   21 | #define rep(i,n) for(ll (i)=0;(i)<(ll)(n);i++)
      |                         ^~~
Main.cpp:70:41: note: in expansion of macro ‘rep’
   70 | V<int> listrange(int n) {V<int> res(n); rep(i,n) res[i]=i; return res;}
      |                                         ^~~
Main.cpp:21:25: note: remove parentheses
   21 | #define rep(i,n) for(ll (i)=0;(i)<(ll)(n);i++)
      |                         ^~~
Main.cpp:70:41: note: in expansion of macro ‘rep’
   70 | V<int> listrange(int n) {V<int> res(n); rep(i,n) res[i]=i; return res;}
      |                                         ^~~
Main.cpp: In function ‘int random_select(V<long long int>&)’:
Main.cpp:21:25: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   21 | #define rep(i,n) for(ll (i)=0;(i)<(ll)(n);i++)
      |                         ^~~
Main.cpp:187:5: note: in expansion of macro ‘rep’
  187 |     rep(i, vals.size()) {val -= vals[i]; if (val<=0) return i;}
      |     ^~~
Main.cpp:21:25: note: remove parentheses
   21 | #define rep(i,n) for(ll (i)=0;(i)<(ll)(n);i++)
      |                         ^~~
Main.cpp:187:5: note: in expansion of macro ‘rep’
  187 |     rep(i, vals.size()) {val -= vals[i]; if (val<=0) return i;}
      |     ^~~
Main.cpp: In member function ‘int Board::try_update_0(double)’:
Main.cpp:208:29: warning: unused parameter ‘thred’ [-Wunused-parameter]
  208 |     int try_update_0(double thred) {
      |                      ~~~~~~~^~~~~
Main.cpp: In member function ‘int Board::try_update_1(double)’:
Main.cpp:213:29: warning: unused parameter ‘thred’ [-Wunused-parameter]
  213 |     int try_update_1(double thred) {
      |                      ~~~~~~~^~~~~
Main.cpp: In function ‘std::vector<std::pair<int, int> > compute_convex_hull(std::vector<std::pair<int, int> >)’:
Main.cpp:445:32: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  445 |             while (hull.size() >= start + 2 && orient(hull[hull.size() - 2], hull[hull.size() - 1], points[i]) <= 0)
      |                    ~~~~~~~~~~~~^~~~~~~~~~~~
Main.cpp: In function ‘std::vector<std::pair<int, int> > build_safe_convex_hull(const std::vector<std::pair<int, int> >&, int&, const std::set<std::pair<int, int> >&)’:
Main.cpp:467:33: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  467 |     for (int i = start_index; i < target.size(); ++i) {
      |                               ~~^~~~~~~~~~~~~~~
Main.cpp: In function ‘std::pair<std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> > > build_hand_path(std::pair<int, int>, const std::vector<std::pair<int, int> >&, const std::pair<int, int>&)’:
Main.cpp:502:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  502 |     for (int i = 1; i < hull.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp:512:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  512 |     for(int i=1; i<hull.size(); i++) {
      |                  ~^~~~~~~~~~~~
Main.cpp:522:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  522 |     for (int i = 0; i < hull.size() + 1; ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~
Main.cpp:527:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  527 |     for(int i=0; i<hull.size() + 1; i++) {
      |                  ~^~~~~~~~~~~~~~~~
Main.cpp: In function ‘void padding(std::vector<std::pair<int, int> >&, pii, int)’:
Main.cpp:540:22: warning: comparison of integer expressions of different signedness: ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  540 |     while(dat.size() < border) dat.push_back(elem);
      |           ~~~~~~~~~~~^~~~~~~~
Main.cpp: In function ‘void simulate_routes(const std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&, const std::set<std::pair<int, int> >&, OutputManager&)’:
Main.cpp:572:20: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  572 |     while (t_index < takahashi_target.size() || a_index < aoki_target.size()) {
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:572:57: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  572 |     while (t_index < takahashi_target.size() || a_index < aoki_target.size()) {
      |                                                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:580:42: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  580 |         pair<int, int> t_next = (t_index < takahashi_target.size() ? takahashi_target[t_index] : t_pos);
      |                                  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:581:42: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  581 |         pair<int, int> a_next = (a_index < aoki_target.size() ? aoki_target[a_index] : a_pos);
      |                                  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp: In function ‘void get_randomize(std::vector<std::pair<int, int> >&)’:
Main.cpp:709:21: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  709 |     for(int i=idx; i<dat.size(); i++) ret.push_back(dat[i]);
      |                    ~^~~~~~~~~~~
Main.cpp: In function ‘ll Main()’:
Main.cpp:725:20: warning: variable ‘POS_CORNER’ set but not used [-Wunused-but-set-variable]
  725 |     pair<int, int> POS_CORNER = pii(0, 0);
      |                    ^~~~~~~~~~
Main.cpp: In function ‘void Main_test(int, char**)’:
Main.cpp:799:9: warning: unused variable ‘cc’ [-Wunused-variable]
  799 |     int cc = 0;
      |         ^~
Main.cpp: In instantiation of ‘void debug(std::vector<_Tp>&) [with T = int]’:
Main.cpp:242:14:   required from here
Main.cpp:65:13: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   65 | for(ll i=1;i<v.size();i++)cerr spa v[i];
      |            ~^~~~~~~~~

Judge Result