Submission #639417

#	Time	Username	Problem	Language	Result	Execution time	Memory
639417		colossal_pepe	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	65 ms	6696 KiB

joi2019_ho_t4

#include <iostream>
#include <vector>
using namespace std;

using ll = long long;

int n, cnt[2][100000], cf[4] = {0, 1, 0, 1}, ce[4] = {0, 1, 1, 0};

ll adjust() {
    ll ret = 0;
    vector<vector<int>> f(2), e(2);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            if (not cnt[j][i]) f[j].push_back(i);
            while (cnt[j][i] > 1) {
                e[j].push_back(i);
                cnt[j][i]--;
            }
        }
        for (int j = 0; j < 4; j++) {
            while (f[cf[j]].size() and e[ce[j]].size()) {
                ret += abs(f[cf[j]].back() - e[ce[j]].back()) + (cf[j] != ce[j]);
                cnt[cf[j]][f[cf[j]].back()]++;
                f[cf[j]].pop_back();
                e[ce[j]].pop_back();
            }
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    ll ans = 0;
    for (int i = 0; i < 2 * n; i++) {
        int x, y;
        cin >> x >> y;
        if (x < 1) {
            ans += 1 - x;
            x = 1;
        } else if (x > n) {
            ans += x - n;
            x = n;
        }
        if (y < 1) {
            ans += 1 - y;
            y = 1;
        } else if (y > 2) {
            ans += y - 2;
            y = 2;
        }
        cnt[y - 1][x - 1]++;
    }
    // cout << ans << '\n';
    // for (int i = 1; i >= 0; i--) {
    //     for (int j = 0; j < n; j++) {
    //         cout << cnt[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    ans += adjust();
    cout << ans << '\n';
    // for (int i = 1; i >= 0; i--) {
    //     for (int j = 0; j < n; j++) {
    //         cout << cnt[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    return 0;
}

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