Submission #1142460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142460		huoi	Coin Collecting (JOI19_ho_t4)	C++17	100 / 100	32 ms	4152 KiB

joi2019_ho_t4

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define INF 9e18

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

    vector<vector<int>> cnt(3, vector<int>(n + 1));
    int ans = 0;

    for (int i = 0; i < 2 * n; i++) {
        int r, c; cin >> c >> r;
        if (r < 1) ans += (1 - r), r = 1;
        if (r > 2) ans += (r - 2), r = 2;
        if (c < 1) ans += (1 - c), c = 1;
        if (c > n) ans += (c - n), c = n;
        cnt[r][c]++;
    }

    stack<int> extra[3];
    stack<int> zero[3];
    for (int j = 1; j <= n; j++) {
        for (int i = 1; i <= 2; i++) {
            if (cnt[i][j] == 0 && extra[i].size()) {
                ans += abs(j - extra[i].top());
                cnt[i][extra[i].top()]--;
                if (cnt[i][extra[i].top()] == 1) extra[i].pop();
                cnt[i][j]++;
            }
        }
        for (int i = 1; i <= 2; i++) {
            while (zero[i].size() && cnt[i][j] > 1) {
                ans += abs(j - zero[i].top());
                cnt[i][zero[i].top()]++;
                zero[i].pop();
                cnt[i][j]--;
            }
        }
        for (int i = 1; i <= 2; i++) {
            if (cnt[i][j] == 0 && extra[3 - i].size()) {
                ans += abs(j - extra[3 - i].top()) + 1;
                cnt[3 - i][extra[3 - i].top()]--;
                if (cnt[3 - i][extra[3 - i].top()] == 1) extra[3 - i].pop();
                cnt[i][j]++;
            }
        }
        for (int i = 1; i <= 2; i++) {
            while (zero[3 - i].size() && cnt[i][j] > 1) {
                ans += abs(j - zero[3 - i].top()) + 1;
                cnt[3 - i][zero[3 - i].top()]++;
                zero[3 - i].pop();
                cnt[i][j]--;
            }
        }
        for (int i = 1; i <= 2; i++) {
            if (cnt[i][j] > 1 && cnt[3 - i][j] == 0) {
                cnt[i][j]--;
                cnt[3 - i][j]++;
                ans++;
            }
        }
        for (int i = 1; i <= 2; i++) {
            if (cnt[i][j] > 1) extra[i].push(j);
            if (cnt[i][j] == 0) zero[i].push(j);
        }
        //for (int i = 2; i >= 1; i--)
            //for (int j = 1; j <= n; j++)
                //cout << cnt[i][j] << " \n"[j == n];
    }

    cout << ans;
}

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

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