Submission #142231

#	Time	Username	Problem	Language	Result	Execution time	Memory
142231		darkkcyan	Coin Collecting (JOI19_ho_t4)	C++14	0 / 100	2 ms	376 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    // return (T)(rng() % range);
// }

int n;
multiset<int> coins[2];
int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    llong ans = 0;
    rep(i, 2 * n) {
        int r, c; 
        cin >> c >> r;

        if (r > 2) {
            ans += r - 2;
            r = 2;
        }
        if (r < 1) {
            ans += 1 - r;
            r = 1;
        }
        if (c > n) {
            ans += c - n;
            c = n;
        }
        if (c < 1) {
            ans += 1 - c;
            c = 1;
        }
        coins[--r].insert(--c);
    }

    // clog << ans << endl;

    rep(i, n) {
        tuple<llong, int, int> temp_ans = {INT_MAX, -1, -1};
        if (len(coins[0]) and len(coins[1])) {
            temp_ans = min(temp_ans, {abs(i - *coins[0].begin()) + abs(i - *coins[1].begin()),
                0, 1
            });
        }

        rep(f, 2) {
            if (len(coins[f]) < 2) continue;
            int u = *coins[f].begin(), v = *next(coins[f].begin());
            temp_ans = min(temp_ans, {abs(i - u) + abs(i - v) + 1, f, f});
        }

        ans += get<0>(temp_ans);
        int u = get<1>(temp_ans), v = get<2>(temp_ans);
        coins[u].erase(coins[u].begin());
        coins[v].erase(coins[v].begin());
        // clog << get<0>(temp_ans) << ' ' << u << ' ' << v << endl;
    }
    cout << ans;

    return 0;
}

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