제출 #1266637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266637		witek_cpp	Coin Collecting (JOI19_ho_t4)	C++20	0 / 100	0 ms	328 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    int M = 2 * N;
    vector<pair<ll,ll>> coins(M);
    for (int i = 0; i < M; ++i) cin >> coins[i].first >> coins[i].second;

    // przygotuj listę celów: (1,1),(1,2),(2,1),(2,2),...,(N,1),(N,2)
    vector<pair<int,int>> targets;
    targets.reserve(M);
    for (int x = 1; x <= N; ++x) {
        targets.emplace_back(x, 1);
        targets.emplace_back(x, 2);
    }

    ll ans = 0;
    // dla każdego celu wybierz najbliższy dostępny coin (brutalne przeszukanie)
    for (auto &t : targets) {
        int best_idx = -1;
        ll best_dist = (ll)9e18;
        for (int i = 0; i < (int)coins.size(); ++i) {
            ll d = llabs(coins[i].first - t.first) + llabs(coins[i].second - t.second);
            if (d < best_dist) {
                best_dist = d;
                best_idx = i;
            }
        }
        ans += best_dist;
        // usuń wykorzystany coin: zamień z ostatnim i pop_back (O(1))
        swap(coins[best_idx], coins.back());
        coins.pop_back();
    }

    cout << ans << "\n";
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63