Submission #639417

#TimeUsernameProblemLanguageResultExecution timeMemory
639417colossal_pepeCoin Collecting (JOI19_ho_t4)C++17
100 / 100
65 ms6696 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...