Submission #1141552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141552		huoi	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	0 ms	328 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define INF 9e18
#define BASE 1e9

void solve() {
    int n;
    cin >> n;

    vector<vector<int>> occupied(3, vector<int>(n + 1));

    auto check = [&](int r, int c) {
        return r >= 1 && r <= 2 && c >= 1 && c <= n;
    };

    auto closest = [&](int r, int c) {
        int ansr = -1, ansc = -1, min_dist = INF;
        for (int i = 1; i <= 2; i++) {
            for (int j = 1; j <= n; j++) {
                if (occupied[i][j]) continue;
                int dist = abs(r - i) + abs(c - j);
                if (dist < min_dist) {
                    min_dist = dist;
                    ansr = i, ansc = j;
                }
            }
        }
        //printf("closest for %lld %lld is %lld %lld\n", r, c, ansr, ansc);
        if (check(r, c)) occupied[r][c]--;
        occupied[ansr][ansc]++;
        return min_dist;
    };

    vector<pair<int, int>> a(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        cin >> a[i].second >> a[i].first;
        auto [r, c] = a[i];
        if (check(r, c)) occupied[r][c]++;
    }

    int ans = 0;
    for (auto [r, c] : a) {
        if (check(r, c) && occupied[r][c] == 1) continue;
        ans += closest(r, c);
    }
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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