Test/AtCoder/abc448_f.test.cpp

View this file on GitHub
Last update: 2026-03-16 19:40:14+09:00
Problem: https://judge.yosupo.jp/problem/aplusb
Link: https://atcoder.jp/contests/abc448/submissions/74165490
Link: https://atcoder.jp/contests/abc448/tasks/abc448_f

Depends on

Code

// #define PROBLEM "https://atcoder.jp/contests/abc448/tasks/abc448_f"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

/*
 * AtCoder Beginner Contest 448 - F Authentic Traveling Salesman Problem
 * https://atcoder.jp/contests/abc448/submissions/74165490
 */

#include "../../Src/Utility/Mo.hpp"
#include <iostream>
#include <cmath>
#include <cassert>
#include <vector>
#include <algorithm>
#include <ranges>
#include <utility>
using namespace std;
int main() {
#ifdef ATCODER
    int N;
    cin >> N;
    vector<pair<int,int>> P(N);
    for (auto& [x,y] : P)
        cin >> x >> y;
    auto ans = zawa::Mo(P);
    ranges::rotate(ans,ranges::find(ans,0));
    long long cost = 0;
    for (int i = 0 ; i < ssize(ans) ; i++) {
        int j = ans[i], k = ans[(i+1)%N];
        cost += abs(P[j].first-P[k].first);
        cost += abs(P[j].second-P[k].second);
    }
    assert(cost <= (long long)7.5e9);
    for (int i = 0 ; i < ssize(ans) ; i++)
        cout << ++ans[i] << (i + 1 == ssize(ans) ? '\n' : ' ');
#else
    int a,b;
    cin >> a >> b;
    cout << a+b << '\n';
#endif
}

#line 1 "Test/AtCoder/abc448_f.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc448/tasks/abc448_f"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

/*
 * AtCoder Beginner Contest 448 - F Authentic Traveling Salesman Problem
 * https://atcoder.jp/contests/abc448/submissions/74165490
 */

#line 2 "Src/Utility/Mo.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Utility/Mo.hpp"

#include <algorithm>
#include <cmath>
#include <concepts>
#include <ranges>
#include <utility>
#include <numeric>
#include <limits>
#include <vector>

namespace zawa {

template <std::signed_integral T>
std::vector<usize> Mo(const std::vector<std::pair<T,T>>& P) {
    if (P.empty())
        return {};
    T minY = std::numeric_limits<T>::max();
    const u64 W = [&]() {
        T minX = std::numeric_limits<T>::max();
        T maxX = std::numeric_limits<T>::min(), maxY = std::numeric_limits<T>::min();
        for (auto [x,y] : P) {
            minX = std::min(minX,x);
            maxX = std::max(maxX,x);
            minY = std::min(minY,y);
            maxY = std::max(maxY,y);
        }
        return std::max<u64>({1,u64(maxX-minX),u64(maxY-minY)});
    }();
    const usize B = [&]() {
        u64 sq = std::max<u64>(1,sqrt(P.size()));
        return (W + sq - 1) / sq;
    }();
    T sub = minY;
    auto makeRank = [&]() -> std::vector<std::pair<T,T>> {
        std::vector<std::pair<T,T>> res(P.size());
        for (usize i = 0 ; i < P.size() ; i++) {
            res[i].first = (P[i].second - sub) / B;
            res[i].second = (res[i].first & 1 ? -1 : 1) * P[i].first;
        }
        return res;
    };
    std::vector<usize> ord1(P.size()), ord2(P.size());
    std::iota(ord1.begin(),ord1.end(),0);
    std::iota(ord2.begin(),ord2.end(),0);
    auto rank = makeRank();
    std::ranges::sort(ord1,[&](usize i, usize j) { return rank[i] < rank[j]; });
    sub -= B / 2;
    rank = makeRank();
    std::ranges::sort(ord2,[&](usize i, usize j) { return rank[i] < rank[j]; });
    auto cost = [&](const std::vector<usize>& ord) {
        u64 res = 0;
        for (usize i = 0 ; i + 1 < ord.size() ; i++) {
            res += abs(P[ord[i+1]].first-P[ord[i]].first);
            res += abs(P[ord[i+1]].second-P[ord[i]].second);
        }
        return res;
    };
    return cost(ord1) <= cost(ord2) ? ord1 : ord2;
}

} // namespace zawa
#line 10 "Test/AtCoder/abc448_f.test.cpp"
#include <iostream>
#line 12 "Test/AtCoder/abc448_f.test.cpp"
#include <cassert>
#line 17 "Test/AtCoder/abc448_f.test.cpp"
using namespace std;
int main() {
#ifdef ATCODER
    int N;
    cin >> N;
    vector<pair<int,int>> P(N);
    for (auto& [x,y] : P)
        cin >> x >> y;
    auto ans = zawa::Mo(P);
    ranges::rotate(ans,ranges::find(ans,0));
    long long cost = 0;
    for (int i = 0 ; i < ssize(ans) ; i++) {
        int j = ans[i], k = ans[(i+1)%N];
        cost += abs(P[j].first-P[k].first);
        cost += abs(P[j].second-P[k].second);
    }
    assert(cost <= (long long)7.5e9);
    for (int i = 0 ; i < ssize(ans) ; i++)
        cout << ++ans[i] << (i + 1 == ssize(ans) ? '\n' : ' ');
#else
    int a,b;
    cin >> a >> b;
    cout << a+b << '\n';
#endif
}