Submission #463841

#	Time	Username	Problem	Language	Result	Execution time	Memory
463841		whoiam	Coin Collecting (JOI19_ho_t4)	C++17	0 / 100	1 ms	204 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

#define range(i, n) for (int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define ar array
using namespace std;

// using namespace __gnu_pbds;
/*
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
*/

typedef long long ll;
typedef double ld;
typedef unsigned long long ull;

const int INFi = 1e9 + 5;
const int maxN = 2e5 + 5;
const int md = 998244353;
const ll INF = 2e18;

double getTime() { return clock() / (double) CLOCKS_PER_SEC; }

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> to(2);
    ll ans = 0;
    range(_, 2 * n) {
        int x, y;
        cin >> x >> y;
        if (y < 1) {
            ans += 1 - y;
            y = 1;
        } else if (y > 2) {
            ans += y - 2;
            y = 2;
        }
        if (x < 1) {
            ans += 1 - x;
            x = 1;
        } else if (x > n) {
            ans += x - n;
            x = n;
        }
        to[y - 1].push_back(x - 1);
    }
    sort(rall(to[0]));
    sort(rall(to[1]));
    range(i, n) {
        pair<ll, int> answ = {INF, -1};
        if (!to[0].empty() && !to[1].empty()) {
            answ = min(answ, {abs(to[0].back() - i) + abs(to[1].back() - i), 0});
        }
        int kek = 2;
        if (to[0].size() < to[1].size()) kek = 3;
        if (to[0].size() >= 2) {
            int sz = to[0].size();
            answ = min(answ, {abs(to[0][sz - 1] - i) + abs(to[0][sz - 2] - i) + 1, kek});
        }
        if (to[1].size() >= 2) {
            int sz = to[1].size();
            answ = min(answ, {abs(to[1][sz - 1] - i) + abs(to[1][sz - 2] - i) + 1, kek ^ 1});
        }
        ans += answ.first;
        if (answ.second == 0) {
            to[0].pop_back();
            to[1].pop_back();
        } else if (answ.second == kek) {
            to[0].pop_back();
            to[0].pop_back();
        } else {
            to[1].pop_back();
            to[1].pop_back();
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int tests = 1;
//    cin >> tests;
    range(_, tests) {
        solve();
    }
    return 0;
}

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